ある特定の検索履歴が何をしても消えません。インターネットオプションや、red~なんとかというファイルで指定してもダメでした。MicrosoftでもＩＥ６で、大量に履歴が残ると起こるもので、未だ解決策はないとＨＰにもありました。

http://homepage2.nifty.com/winfaq/c/ietrouble.html#584

↑もしかして、Easy CD CreaterっていうCD作成ソフトをお使いではありませんか？　上記URLにありますが、その場合は「Easy CD Creater を 4.05 以上にアップデート」すると解決するそうです。

どのソフトが入っているか分からない場合は、「スタート」の「設定」の「コントロールパネル」で「アプリケーションの追加と削除」の「インストールと削除」タブを見てみてください。Easy CD Createrがあればそこから確認できるはずです。（パソコンに入っていてもココに表示されないタイプのソフトも多々ありますけれども、Easy CD Createrは表示されます）

で、もし、Easy CD Createrが入っているときは、「スタート」の「プログラム」で、「Roxio Easy CD Creater」を起動してみて、画面右上の「ヘルプ」の「バージョン情報」で、バージョンが確認できるので、もしも、4.02か4.03バージョンでしたら、以下のアップデータをダウンロードしてお試し下さい。

• Easy CD Creator Ver4.02/4.03-->Ver4.05 アップデート プログラム
  • http://www.roxio.jp/support/download/ecdc4/ecdc405.html

もしもハズレでしたらすみません。