>>I suggest asking this question here
>>
>>http://social.msdn.microsoft.com/Forums/en-US/transactsql/threads
>>
>>Check also http://social.msdn.microsoft.com/Forums/en-US/transactsql/thread/3b2b23dc-be6c-4a06-86af-c582aee81e41 on a very similar topic which may apply to your case.
>
>I do understand that the presence of the INCLUDE index may affect the base indexes. I have had this situation a while ago that those indexes were conflicting with the base indexes. Once we removed them, the application started to run optimized again. There seems to be some corelations here. As I said, I had to remove all indexes and recompile them all again. That resolved the issue. But, if I had only recompiled the INCLUDE type indexes, this wouldn't have done it.
>
>There is also an important note on that topic. One mentioned that he does this rebuild all at midnight. The problem with that, especially on Web apps, is that if you do that while the application runs, for the time that one specific table loses its indexes, this may bring the server down assuming that a specific hit requires an index.

BTW, unrelated observation, but we discussed this point before and I see that you haven't fixed that query yet:

http://sqlblog.com/blogs/aaron_bertrand/archive/2009/10/06/bad-habits-to-kick-order-by-ordinal.aspx