CSSの:visitedセレクタでは、セキュリティー上の都合でcolorやbackground-colorなどが使えなくなっています。

a:visited {
  color: red;
}

関連する話題が楽天ad4Uです。

楽天ad4Uは、Flashオブジェクトの中に数千個のURLへのリンクを埋め込み、それぞれのURLを訪れた形跡があるか否かによって、ユーザーのアクセス動向を調べる。このようなことができるのは、ウェブブラウザーがURLへのリンクを表示する際に、訪問済みのURLと未訪問のURLとで異なる色で表示することについて、そのどちらの状態であるか、Cascading Style Sheets（CSS）をJavaScriptによって参照することで判別できるためである。

楽天ad4U – Wikipedia
https://ja.wikipedia.org/wiki/%E6%A5%BD%E5%A4%A9ad4U

少し不便ですが、プライバシーのことを考えると使えない方がいいですね。

リンク

html – background-color doesn’t work on a:visited but it works if i add any background color to a {backgroud:#fff}, Is it a bug? – Stack Overflow
http://stackoverflow.com/questions/7647459/background-color-doesnt-work-on-avisited-but-it-works-if-i-add-any-background