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