投稿後に CatTail様の返信を確認しまして、編集・追記しています。
CatTail様の手法のほうが手軽に確認できますので、まずはそちらのご確認をされることをお勧めします。
ここまで追記
----------------------------------------
こんにちは、naginoです。
DBCC UPDATEUSAGE では状況変化無しとのこと、了解しました。
パフォーマンス関連のチューニングや障害対応は、原因を詳細に分析してから根本対策を行う方法と、症状を見ながら対症療法で Try & Error を繰り返す方法とありますが、いずれにせよ環境依存となりますので、このような公式サポートではない掲示板では解決するかどうか確実ではない点、並びに要する時間が大きくなる点、あらかじめご承知おきください。
お急ぎの場合、あるいは確実な解決が必要な場合は、有償サポートをご検討ください。
とりあえず tempdb ですが、こちらは領域の自動拡張と切り捨てのオーバーヘッド、ファイルの分割による排他の回避、ディスクの RAID 構成ですとか、そういった箇所を念頭において記載しておりました。
幸いドライブが別とのことですので、一旦保留で良いかと考えます。
（パフォーマンスカウンタの Logical Disk の Queue Length などで負荷を測定できるため）
以下は、さしあたって有償サポートを使用されない場合にご確認ください。
それで、方策は様々あるためどうするか難しいのですが、とりあえず状況の整理からでしょうか。
まず、今回問題となっているストアドプロシージャが以下のページの「カーソル」に記載があるケースに該当しないかご確認ください。
http://msdn.microsoft.com/ja-jp/library/ms143359(SQL.90).aspx
上記に限らず 2000 と 2005 は色々と実装が異なる点があるため、結果が変化する、パフォーマンスが変化するなど、様々な形で挙動が変化します。
（今回のケースで現時点で思い当たるのは上記ですが、他にも可能性のある事項があるかもしれません）
また、今回問題になっているストアドプロシージャを単体で実行した場合（例えば SQL Server Management Studio のクエリウィンドウで実行するなど）、どの程度の時間がかかりますでしょうか。
そこで 5分程度かかっている場合、CPU、ディスク、メモリのいずれがボトルネックになっていますでしょうか。
負荷の状況はシステムモニタで確認できます。
http://msdn.microsoft.com/ja-jp/library/ms191246(SQL.90).aspx
明確なボトルネックがある場合は、そこをヒントに原因を突き止められるかもしれません。
あと、ユーザデータベースと tempdb それぞれの照合順序、サイズ、使用可能領域、互換性レベル、自動圧縮の設定はどのようになっていますでしょうか。
それぞれ SQL Server Management Studio のオブジェクトエクスプローラ上で 「DB を右クリック」 ＞ 「プロパティ」と操作していただくと開く、プロパティウィンドウの「全般」と「オプション」で確認することができます。
ちょっと情報元を探しきれていないのですが、ユーザデータベースと tempdb とで照合順序が異なる場合、ソートの順序が異なるためクラスタ化インデックスのソート順が使えずにソートしなおすことなどがあり、パフォーマンスが劣化することがあったと思います。
意外とストアドプロシージャの再コンパイルや、tempdb の拡張だけで解決しそうな気もしますが・・・少々しっくりこないところがあります。
ご参考になれば幸いです。
