インターネットオプションのホームページ設定を変えれば良いんでないのか？

（1）常駐を停めて（「スタート」「ファイル名を指定して実行」「msconfig」「OK」「システム構成ユーティリティ」「スタートアップ」すべての項目のチェックを外し「適用」「OK」再起動）、その後アンインストール（Administratorでログオン後や、セーフモードで削除、レジストリキー操作など）

（2）システムの復元
参考URL

（3）システムを再セットアップ（リカバリ）

（4）既にRe*Clean *** をインストールしている場合のアンインストール削除方法
http://www.geocities.co.jp/Playtown-Yoyo/6130/notes/regclean-pro.htm
「Re*Clean ***」ウィンドウの上部「設定」「全般」「プログラムコントロール」「閉じるボタンでアクションを選択:」「Re*Clean ***を終了する」「適用」
「Re*Clean ***」ウィンドウ「×」で終了
不安をあおって有償版をすぐ買うよう誘導するウィンドウが表示されても無視
「スタート」「すべてのプログラム」「Re*Clean ***」「Re*Clean *** をアンインストールする」Windowsのコントロールパネルにある「プログラムの追加と削除」（XP）、「プログラムと機能」（Vista/Windows 7）から「Re*Clean ***」「Re*Clean ***」がインストールされてるフォルダ「C:\Program Files\Re*Clean ***\」をエクスプローラで開いて「unins000.exe」ファイルを実行
　削除を始めようとすると、「Re*Clean ***」が再び起動し、エラーの”半分”を無料で修復するとして引き留め工作が始まる場合あり、無視し、「アンインストールを行います」
「Re*Clean *** とその関連コンポーネントをすべて削除します。よろしいですか？」「はい」

アンインストール削除できない場合・・・
アンインストール支援ソフト（無料）を使って削除、セーフモードで削除、Administratorでログオン後削除など

私もXPからWin7に移行して同じ現象にあいました、色々と調べまわって得た解決方法は、コントロールパネルのプログラムの追加と削除で、Yontoo　というプログラムを削除すると解決しました。
全くインストールした覚えがないのに、どこかのサイトを閲覧した時に、勝手にインストールされてしまったようです。
Win7移行当初は、セキュリティソフトに無料の、MicrosftSecurityEssentialsを使用していましたが、セキュリティソフトをかいくぐって、勝手にインストールされてしまったようです。
私の環境では、IE9とFirefoxで現象が発生していて、IEやFirefoxの設定などを、どう変更しても改善せず、プログロムの追加と削除を調べたら、インストールした覚えのないYontooというソフトがあり、ネットで調べると、不正な広告を表示する、悪質な一種のウイルスである事が判明し、削除する事で解決しました。
その後、セキュリティソフトは、キャノンのESET Smart Securityに変更して、その後は、問題は発生していません。

下記のようなアドレスがホームページとして登録されていませんか？

http://search.babylon.com/

「Babylon Search」という検索サイトが登録されてしまっているので
IEを起動したときに例の広告表示がでてくるわけです。

ぱっと見は、シンプルなgoogle検索画面のようですが、
まったく違うサイトです。

ツール＞インターネットオプション＞ホームページ　のところで
ご自身の好きな検索サイトなどに登録しなおしたらOKですよ。

/3です。
本人からのレスがないようですが、
>ご回答の(1)常駐を停めて（「スタート」「ファイル名を指定して実行」・・・辺りから、もう理解できません。
理解する必要はありません。
私が引用した内容は全部嘘だと思ってかまいません。実際嘘なんですから。
やるべき事はBabylon Toolbarを削除することのみです。