>>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?
>
>No the execution plan remained as is. I just do not understand why it was extremely fast for a certain period of time. There was some additional records being added. And, that seems to have pushed the optimization off.

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?