スパイウェアが検出されないんんですが

「FileMon」や「Autoruns」で突き止められると思いますね。

スパイウエア対策はWebrootのSweeper君がお勧めです。

対策ソフトのアップデートはしているか、バージョンは新しいのを使っているか、どうなんでしょう？

最新のスパイウェアにはアップデートしていないと、全く無力です。
もししていないなら、アップデートしてから再度検索してみてください。

>初心者では解決できないのでしょうか。

いつまでたっても初心者であれば、いつまでたっても解決できません。

>またこのままでにしておくとパソコンに悪影響がありますか？

今の症状だけでは大した問題はないと思います。
しかし、今後、どのようなスパイウエア、ウィルスに感染するかはわかりません。
すでに感染しているが、あなたが気がつかないというケースもあります。

ANo.5　最後の行下記に訂正です。

（誤）「O4 - 」デスクトップ始まる行。

（正）「O4 - 」で始まる行。

>出会い系ページ

ということは、日本製のスパイウエアですから「Ad-Aware SE」や「Spybot-S＆D」は、多分対応しません。

>そのページは閉じればきえるんですが・・・

おそらくスクリプト系のファイルがスタートアップに登録されているのだと思います。

「HijackThis」を使って見てください。

☆HijackThisによるレポート出力と手動でのスパイウェア除去
http://www.higaitaisaku.com/hijackthis.html

ただし、使い方がわからずに操作すると重大な支障が発生することがあります。
十分な知識なしに指示されたこと以外の操作をしないように注意してください。

１．「C:\HJT」と言うフォルダを作っておきます。
　以下、このフォルダを「HJT」フォルダと呼ぶことにします。
　
２．下記サイトから「HijackThis」をダウンロードします。
http://www.download.com/HijackThis/3000-8022_4-1 …

３．ダウンロードされたファイル「hijackthis.zip」を解凍すると「HijackThis.exe」と言うファイルができます。

４．「HijackThis.exe」を「HJT」フォルダに保存します。
　　以降このフォルダにログファイルやバックアップが保存されるようになります。
　　
５．IEの画面をすべて閉じた後「HijackThis.exe」を起動し「Do a system scan and save a logfile」をクリック

６．「HijackThis」の画面が開かれシステムをスキャンした結果が一覧表示され、「hijackthis.log」と言うファイルが「HJT」フォルダに自動的に保存されます。

７．「hijackthis.log」の画面で下記の行をすべて補足欄に貼り付けてみてください。

「O4 - 」デスクトップ始まる行。

　どこかで「このページをホームページ(最初に表示するページ)にする」設定にしたのではないでしょうか？

IEを起動して「ツール」→「インターネットのオプション」
(もしくはデスクトップのIEのアイコンを右クリックして「インターネットのプロパティ」
→「全般タブ」の一番上の「ホームページ」の所のURLと書き換えるか
好きなサイトを表示して「現在のページを使用」を押す。
→「OK」を押す。
再起動したら大丈夫だと思います。
万一、再度同じサイトを表示する様でしたら、スタートアップ等に何かないか確認してください。
「ファイル名を指定して実行」で「MSCONFIG」と入力して確認する事ができます。
また、スパイウェア対策だけでなく、ウイルス等を含む「マルウェア対策」全般を行ってください。

スパイウェアのスキャンはウイルス対策ソフトですか？

ウイルス対策ソフトで対応できるスパイウェアは少ないので、SpyBot-Search & DestroyやAd-aware SEでスキャンしてみてください。
セーフモードでないとスキャンできないスパイウェアもありますのでセーフモードでスキャンしてください。
http://www.higaitaisaku.com/menu5.html

スパイウェア検索および削除のソフトは何をご使用になってるんでしょうか？

SpybotとAd-awareが有名ですが、どちらもお使いになったほうがいいですよ。
違うものを検索削除してくれるので。

ただ単に、使用しているブラウザのスタートページが書き換わっているだけではないでしょうか？この場合スパイウェアなどはまったく検出されません。

ＩＥを使用しているのなら、[ツール] - [インターネットオプション]からホームページを自分で書き換えれば出会い系ページは出てきません。