Please can you post the execution plans as .sqlplan files? http://www.sqlservercentral.com/articles/SQLServerCentral/66909/

There's a lot of important information which is not present in a copy-paste of part of the text plan.

Table and index defs would help a lot too.