>If the Statistics have not been updated, you may have wrong estimates. Also, did you try comparing original number of IO read operations with the new one? May be it increased dramatically because of newly added records?

Well, now that I am thinking of it, I can simulate that also on the test server. And, on that one, only 10 to 20 records were added. The execution shows the Key lookup at 66% down the Nested loops (inner join). That one shows a 0% cost.