SQL Performance Issues

Since everything has been anonymized, it's hard to really grasp what is going on here exactly, but these are definitely two different queries. The choice the optimizer has made is influenced in part by the filters on the query, and these queries have two distinct sets of filters – they're close, but not the same (or at least it's not possible for me to tell if they're not identical). If you look at the Query Columns tab in Plan Explorer, you can see this clearly. Here is the fast plan with more reads but no key lookup:

And here is the one with the key lookup and much higher overall cost:

If you want more specific guidance, sorry, but you'll have to post a non-anonymized version of your .queryanalysis file. Then we can match up these column names to their filters, see the expressions involved, and compare the two versions of the query.