I wouldn't call it shitty -- I'd call it pretty damn clever. Better to discover and publicize it rather than letting such a technique slip under the radar of the people who want to prevent such an attack.

I think that a greasemonkey script could probably fish out and change the color back to browser default, since greasemonkey fires on DOMContentLoaded.

You think there's any way that stuff like this hasn't been going on for a long time? Privacy has been redefined. Get over it.

Perhaps a Greasemonkey script or Add-On could intercept attempts to examine the color of visited links, and display a warning to the user or report the site to a central clearinghouse?