Here are suggestions from my friends:

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

check if auto statistics is turned on - suggestion by Denis Gobo
------------------------------------------------------------------------------------------
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.

Fill Factor will not solve the problem, but it may alleviate the problem so that his nightly index rebuilds are sufficient to maintain peak performance throughout the day. - suggestion by George Mastros
------------------------------------------------------------------------------------------------------------------------------------
He also mentioned, that he has a great respect for you for asking questions at your own site.

See also http://social.msdn.microsoft.com/Forums/en-US/transactsql/thread/87574be0-2fde-4db0-b499-9883a2d4dcaf

Looks like you have regular index and combo index. I think you don't need the regular one.



>This one is starting to get on my nerves. I have been trying to find a workaround since two months. Basically, if I index the entire table with the following script, the index in regards to the SQL command shown after the script will get optimized. Then, after a while, it starts to take about 1 to 4 seconds to return the query. That query should be instant. Before, I was running that script once every two weeks. So, I decided to add it into my robot to have this to be executed at midnight. Even by executing that script every night, it still get non optimized after a few hours. I do not want to have to run this script every hour. This doesn't make any sense. Something is not done right. I am trying to figure out what I do wrong in that way I index the table.
>
>Here is the script to index:
>
>

>DECLARE @indexName nvarchar(128)
>DECLARE @dropIndexSql nvarchar(4000)
>DECLARE @Constraint_Name nvarchar(128)
>DECLARE @SQL varchar(4000)
>DECLARE @Message varchar(400)
>
>Raiserror('Removing primary key...',0,1) With Nowait
>
>SELECT @Constraint_Name = Constraint_Name FROM INFORMATION_SCHEMA.KEY_COLUMN_USAGE WHERE Table_Name='Reply'
>if @@rowcount = 1
>   BEGIN
>      SET @SQL='ALTER TABLE Reply DROP Constraint '+@Constraint_Name
>      BEGIN TRY
>         EXECUTE(@SQL)
>      END TRY
>      BEGIN CATCH
>         SET @Message='Error: Problem removing index '+@Constraint_Name
>         Raiserror(@Message,0,1) With Nowait
>         SET @Message=ERROR_MESSAGE()
>         Raiserror(@Message,0,1) With Nowait
>      END CATCH
>   END
>
>DECLARE tableIndexes CURSOR LOCAL FOR
>SELECT name from sys.indexes where is_primary_key=0 and object_name(object_id)='Reply'
>
>OPEN tableIndexes
>FETCH NEXT FROM tableIndexes INTO @indexName
>WHILE @@fetch_status = 0
>BEGIN
>   SET @dropIndexSql = N'DROP INDEX [Reply].[' + @indexName+']'
>   BEGIN TRY
>      SET @Message=@dropIndexSql
>      Raiserror(@Message,0,1) With Nowait
>      EXEC sp_executesql @dropIndexSql
>   END TRY
>   BEGIN CATCH
>         SET @Message='Error: Problem removing index '+@indexName+' from Reply'
>         Raiserror(@Message,0,1) With Nowait
>         SET @Message=ERROR_MESSAGE()
>         Raiserror(@Message,0,1) With Nowait
>   END CATCH
>   FETCH NEXT FROM tableIndexes INTO @indexName
>END
>
>CLOSE tableIndexes
>DEALLOCATE tableIndexes
>
>Raiserror('Creating primary key Numero...',0,1) With Nowait
>
>BEGIN TRY
>  ALTER TABLE [Reply]
>  ADD CONSTRAINT ReplyNumero PRIMARY KEY (Numero)
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating primary key Numero...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index AddUser...',0,1) With Nowait
>
>BEGIN TRY
>   CREATE INDEX [AddUser] ON [Reply] ([AddUser])
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index AddUser...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index AddDate...',0,1) With Nowait
>
>BEGIN TRY
>   CREATE INDEX [AddDate] ON [Reply] ([AddDate])
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index AddDate...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index ModUser...',0,1) With Nowait
>
>BEGIN TRY
>   CREATE INDEX [ModUser] ON [Reply] ([ModUser])
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index ModUser...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index ModDate...',0,1) With Nowait
>
>BEGIN TRY
>   CREATE INDEX [ModDate] ON [Reply] ([ModDate])
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index ModDate...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index NoThread...',0,1) With Nowait
>
>BEGIN TRY
>   CREATE INDEX [NoThread] ON [Reply] ([NoThread])
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index NoThread...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index NoMember...',0,1) With Nowait
>
>BEGIN TRY
>   CREATE INDEX [NoMember] ON [Reply] ([NoMember])
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index NoMember...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index Read...',0,1) With Nowait
>
>BEGIN TRY
>   CREATE INDEX [Read] ON [Reply] ([Read])
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index Read...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index combo IndexCombo1...',0,1) With Nowait
>
>BEGIN TRY
>   IF NOT EXISTS (SELECT * FROM sys.filegroups WHERE Name='Reply')
>      ALTER DATABASE UniversalThread ADD FILEGROUP Reply
>   IF NOT EXISTS (SELECT * FROM sysfiles WHERE Name='Reply')
>      ALTER DATABASE UniversalThread ADD FILE (Name='Reply',FileName='d:\Data\Universal Thread\Reply.ndf') To FileGroup Reply
>   CREATE INDEX [IndexCombo1] ON [Reply] ([NoMember]) INCLUDE ([NoThread]) ON [Reply]
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index combo IndexCombo1...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>
>Raiserror('Creating index combo IndexCombo2...',0,1) With Nowait
>
>BEGIN TRY
>   IF NOT EXISTS (SELECT * FROM sys.filegroups WHERE Name='Reply')
>      ALTER DATABASE UniversalThread ADD FILEGROUP Reply
>   IF NOT EXISTS (SELECT * FROM sysfiles WHERE Name='Reply')
>      ALTER DATABASE UniversalThread ADD FILE (Name='Reply',FileName='d:\Data\Universal Thread\Reply.ndf') To FileGroup Reply
>   CREATE INDEX [IndexCombo2] ON [Reply] ([NoMember],[Read]) INCLUDE ([NoThread]) ON [Reply]
>END TRY
>BEGIN CATCH
>   Raiserror('Error: Problem creating index combo IndexCombo2...',0,1) With Nowait
>   SET @Message=ERROR_MESSAGE()
>   Raiserror(@Message,0,1) With Nowait
>END CATCH
>

>
>Here is the command that is affected by the index when it becomes non optimized:
>
>

>DECLARE @NoMember Integer
>
>SET @NoMember=1
>
>SELECT Thread.Numero,Thread.Title,Thread.Url,Thread.AddDate
> FROM (SELECT TOP 10 Reply.NoThread FROM Reply (NOLOCK)
> WHERE Reply.NoMember=@NoMember ORDER BY 1 DESC) Temp
> INNER JOIN Thread ON Temp.NoThread=Thread.Numero 
>

>
>Right now, the result is:
>
>Duration: 1.7187 Count: 10
>
>When I index again, for a few hours after that, the result would be optimized such as:
>
>Duration: 0.0156 Count: 10
>
>The index that is affected is as follow and is at the end of the script just before the last index that is being built with the INCLUDE syntax:
>
>

>CREATE INDEX [IndexCombo1] ON [Reply] ([NoMember]) INCLUDE ([NoThread]) ON [Reply]
>