Macを教える・教わるコミュの【アプリ】一度利用したサイトの広告がやたらと表示されるようになったのですが

機種：MacBook Pro 13.3"　CPU：2.7 GHz Intel Core i7
メモリ：4Gx2　OS：X 10.7.5
アプリ：Safari 6.0.4

トラブルというわけではないのですが、ホテルの予約をするために利用したサイトの広告が、別のいろいろなサイトの広告バナーに表示されるようになって、気になっています。

まずは、cookieのせいか？と思って、その旅行サイトのデータを消したのですが、一部のページはその広告が消えてそのまま空きスペースになったのですが、それでも消えないページがあります。
その他にデータが記録されていることが考えられるでしょうか？

他のブラウザ（Google Chrome）では、その旅行サイトは一度も表示してません。そして広告が表示されるサイトの同じ場所には、別の広告が表示されます。

環境設定のcookieの項目を見て気がついたのですが、cookieの他にローカルストレージという文字がありまして、cookie的な機能が拡張されているようですね。
下調べしたサイト
「Safariのアクセス速度が遅くなったら・・。Local Storageを削除。・・・」
http://powerapple.at.webry.info/201103/article_1.html
「W3C - 『Web Storage』日本語訳 - HTML5.JP」
http://www.html5.jp/trans/w3c_webstorage.html

Macには、セキュリティソフトを入れてないので、気になりだすと安心してネットで買い物とかも出来なくなります。
なにか教えていただければ幸いです。
どうぞ、よろしくお願いいたします。