>>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.

If we want to avoid key lookup, we want to create covering index (e.g. the index that will include all the columns used in the query). This usually provides the optimal performance for the query, but it makes a wide index and so DML operations suffer.

So, the choice is yours.