インデックスのフラグメンテーションではないですか?
ALTER INDEX でフラグメンテーションの解消と、統計情報の更新をデータベース全体にかけるなど。
詳しくは BOL を参照してください。
統計情報の更新したときにはデータが大量に増えていたりしませんでしたか?
できれば論理 CPU 数分のデータファイルを tempdb とユーザデータベースに施して、クラスタ化インデックスを GUID のような不定期になるようなものにして、I/O 分散させて高速化を図るということもありだと思います。
クラスタ化インデックスはデータの並び順を保証するので、クラスタ化インデックスを設定した Column に途中の値を挿入するとフラグメンテーションが発生してどうしようもない状況になります。
定期的にインデックスのフラグメンテーションの解消をする必要があるでしょう。
ただ、今回は再作成しているということなので、違うかも知れませんが、もしクラスタ化インデックスを主キーにしてあって、再作成していないのであれば、フラグメンテーションしている可能性がありますので解消してみてください。
最後に、できれば SQL Server 2005 の Service Pack と HotFix の適用状況も書いてください。場合によってはバグかもしれないので。