Safari5(及び Safari4.1) では :visited の挙動に大きな修正が入っています。

Safari 5.0 および Safari 4.1 のセキュリティコンテンツについて

対象となるバージョン:Mac OS X v10.4.11、Mac OS X Server v10.4.11、Mac OS X v10.5.8、Mac OS X Server v10.5.8、Mac OS X v10.6.2 以降、Mac OS X Server v10.6.2 以降、Windows 7、Vista、XP SP2 以降

影響:悪意を持って作成された Web サイトにアクセスすると、ユーザがアクセスしたサイトを特定できる可能性がある。

説明:WebKit による CSS で訪問済みの疑似クラスの処理に、デザインの問題が存在します。悪意を持って作成された Web サイトにアクセスすると、ユーザがアクセスしたサイトを特定できる可能性があります。このアップデートでは、訪問したリンクかどうかを基にしたスタイルページへの Web ページ機能を制限します。

これは4月に公開された Mozilla Developer Preview (Number 4) と同じ内容のもので、 JavaScript の getComputedStyle() などと組み合わせることで、訪問済みのサイトを取得することができてしまう、というもので Bugzilla では2002年から議論が続いていたものです。

こちらの詳細は次のページをお読み下さい。

行動ターゲティング広告にも影響が

この技術は現在行動ターゲティング広告でも使われています。その1つにドリコムの ad4U があります。

ad4U:ドリコムの次世代行動ターゲティング広告技術サービス

CSSのvisited擬似クラスに対し訪問済みか否か識別できる値を入力した上で、カテゴリ分けされたURLリストをサーバーから配信。
訪問済みカテゴリを大まかに判断する仕組みです。このマッチング処理はすべてブラウザ上で行なわれます。

この技術を使用している 楽天ad4U では Firefox のみ対応ブラウザから外されていますが、Safari5 でも利用できなくなっていると考えて良いでしょう。

行動ターゲティングサービスの説明とその無効化について

Firefoxでは該当機能の改修が検討されており、将来的に利用出来なくなる可能性があるため、対応ブラウザから外すことに致しました。ご了承の程、宜しくお願い致します。

CSS で背景画像が変わらない?

また、制作面では今回の変更で :visited に指定できるプロパティが大きく制限されています。
その中で特に影響がありそうな部分の1つに :visitedbackground-image などが指定できなくなる、ということがあります。

未訪問リンクと訪問済みリンクの区別を background-image でのみしか指定していないサイトでは、それらの区別がつかなくなっていますので修正が必要かもしれませんね。

関連リンク