>>Are the statistics being updated? When you create an index the stats get updated but if they are not updated after that the optimizer might choose a wrong plans since it doesn't know how many rows for a specific criteria are in the table
>
>It cannot be related to that as I just observed that when it is slow, the execution plan is the same as when it is fast, which is the case right after I reindex.
>
>Auto Create Statistics is turned ON, so is Auto Updated Statistics. But, this is the recommended setting.
>
>>I'm guessing that the Reply table is rather busy. It could be index fragmentation that is causing the problem. You may want to suggest that he use a different fill factor. The default fill factor is 0 (which actually means 100%). With a 100% fill factor, the data pages are completely filled when the index is recreated. So, whenever a row is added to the middle of the index, you are guaranteed a page split. I would recommend he use a fill factor = 90%. Try that. If the performance continues to degrade rapidly, then try a smaller fill factor. I wouldn't go below 80 though.
>
>Yes, the Reply table is rather busy. But, it's not like hell. You can extrapolate the numbers based on the number of messages we have here in one day, where most of them generate replies.
>
>I do not know where the fill factor is. Is this something that relates at the database level or on each index?
>

The fill factor is for each individual index. Check the syntax of CREATE INDEX command in BOL.

>>He also mentioned, that he has a great respect for you for asking questions at your own site.
>
>I am not sure I understand the comment. Should site owners avoid using their own product? As for me, I use this site as my prime and only support site, but to Google from time to time. As a site owner, I think it also shows the example to the site members.
>

It's in comparison with another website. I can send you later how exactly he phrased it - may be it'll be more clear.

>>See also http://social.msdn.microsoft.com/Forums/en-US/transactsql/thread/87574be0-2fde-4db0-b499-9883a2d4dcaf
>
>I do not know what is in reference in that page to this thread.
>
>>Looks like you have regular index and combo index. I think you don't need the regular one.
>

In that thread I asked a question relevant to your case. Unfortunately, none answered it yet.

>I started to use that to achieve a better performance. It seems that the more the table grows, so as the indexes, that the usage of those combo index is necessary. If someone could show me other way, I would be glab to get rid of those.

I believe you have combo index and the same non-combo. Sounds to me you can keep combo and get rid of another one.