>>Data Manipulation Language. UPDATE, INSERT, DELETE and MERGE operators are usually DML operators.
>
>Ok, reason I mentioned this is because this situation came back. The index hasn't changed, the code hasn't changed. However, once I adjusted the SQL command two weeks ago, this was extremely fast. Now, a few weeks after, we run into the same problem again. I still have the 66% lookup that is in the execution plan which I cannot get rid.

What is the index level fragmentation and what is the exact query (or the pseudo-query with good resemblance)?

I also think you can have a good response if you ask your question (in addition to asking here) in this forum
http://social.msdn.microsoft.com/Forums/en-US/transactsql/threads

The reason I suggest the external forum is there you'll find several SQL Server MVPs that crack such complex problems.

Also, did the execution plan change comparing with the original?

In addition, have you tried manually update statistics for involved tables?