Solved for sites that include third-party code
The Caja project addresses this problem for websites that want to include third-party HTML without allowing JS in it to sniff history or do other nasty things. It uses a similar method -- limit how fancy styles can get for :visited (nothing that changes layout), and then present the unvisited styles whenever JS tries to observe computed CSS.
http://code.google.com/p/google-caja/