それは仕様。

http://www.w3.org/TR/2011/REC-css3-selectors-20110929/#the-link-pseudo-classes-link-and-visited
Note: It is possible for style sheet authors to abuse the :link and :visited pseudo-classes to determine which sites a user has visited without the user's consent.
UAs may therefore treat all links as unvisited links, or implement other measures to preserve the user's privacy while rendering visited and unvisited links differently.

の範囲内の動作。