Since this information is very useful to an attacker, Mozilla is preparing to break compliance with APIs to stop this vector:
getComputedStyle()et al. will not leak information about page visited status
- Differences in styling for visited links versus styling for unvisited links will be restricted against changes in opacity, visibility, and many other ways
- These rules propagate and are immune to CSS tricks like combinators and nesting
But this issue is too big to settle for a "solution" that breaks the API, does so ungracefully, and still does not solve the problem. Here is a demonstration that will still work if Mozilla goes through with this cowboy (read: Microsoft) attitude to web standards. The first one tells you if you visited purple.com before and the second one tells you if you have logged in to Zecco.com:
You could probably do a better job than me of styling these elements, but either way, the attack vector still exists.