>>If you can post the actual query (or query closely resembling the original with structures and indexes) I may try to see what can be done to optimize it.
>>
>>Also, if needed, you can use query hints and even specify which index you want it to use (INDEX hint). You may want to experiment with this and see if you can get a better plan / performance.
>>
>>Also make sure to have DB compatibility level matching the version of DB.
>>
>>Finally, make sure you're on the latest SP for your SQL Server version.
>>
>>Also, avoid having DATEDIFF function in the right part of the query expression.
>
>We have been working on that this afternoon and this is the most difficult one we have been dealing with so far. One of the problem is that the primary key, which is a clustered index, seems to have priority over an index that we have created just to satisfy the SQL where clause. As this is the case, and knowing that a clustered index cannot include fields, it makes it difficult for the execution plan to use the other index on the primary key we have created, which include the related fields.
>
>We have been thinking of what I do here on the Universal Thread, thus, for the search, bumping the search result into a temporary table and using that in the list after. Then, only the search request takes longer and the navigation in the list is fast because we do not have to do the search again.
>
>We also have been thinking of adding an additional field or even a numeric value for the date which we would then use for the queries instead of using the regular date fields, which are not as optimized as an integer field.
>
>Usually, with the execution plan, we are able to resolve the issue in minutes. But, this one, it is a real mystery.

I can only repeat my initial advice - if everything fails, try adding Index expression into the query. E.g. add Index hint.