Ad-aware SEを使ってますが、（Ｖ２００でも）Cookieは良く検出されますね。
ただ、本当のスパイは少ないようで、ほとんどが広告用のCookieみたいです・・・

Microsoft AntiSpywareを使ってます。
無料だし、まぁまぁです。

窓２０００では
ewido security suite（free機能のみ）
Ad-aware SE
Spybot - Search & Destroy
これで偶々気が向いたら上のどれかでスキャン＆除去して別の一つでチェック。
javacoolsoftwareのフリーソフト等複数でガード（含む免疫化機能常駐はspywearguardのみ）
ですね。
cookieと偶にレジストリくらいして、他はほとんど無いです。
ただ先日PC-Clean（フリー（お試し版？））でスキャンを試したところ一つだけ入ってました。（常駐はさせてません）

9X系はewido使えないしPC-Cleanも一人1台1つみたいですね。

デフォルト設定だと、IEの履歴、最近使ったファイル、名前を指定して実行、の履歴も検出の対象になっていると思います。OSだけでなく、メジャーなソフトの「最近使ったファイル」とか、何かしら登録されていると、個人情報が勝手に記録されたと見なすようです。
cookieは、広告バナー付きの無料スペースに作られた個人サイトにアクセスすると、自動的にどんどん登録されていきますね。
何をもってスパイと見なすかは人それぞれの解釈の違いでしょう。
XPだと、OS自身が色々な状態をレジストリに記録するため、どうしても消せないエントリがいくつかできてしまいます。

AT機ですが、最近、IE Privacy Keeper 2を使い始めました。
9X系も使えるし、firefox対応でよろこんでいたら、firefoxがNew versionになるわで...

easyfoxさんの所で日本語化ファイルが配布しているから、割合使いやすいと思います。