There are a bunch of these exploits — I remember one a few weeks ago that posed as a mind-reading survey — and I think they can only be well and truly solved by a same-domain policy for :visited links. In short, don't apply :visited styling to a link unless that link is the same domain as the host page. This is the general security model on the rest of the web and it'd work here.