That would break aggregator sites like HN and Reddit (although really they should really be maintaining the visit history themselves, as they do with Reddit Gold users).
I tried to use the history tracking that comes with Reddit Gold for about a week and it was virtually useless. After browsing on my phone and two computers only like 1 in 10 of the links would correctly show up as purple on the other devices (even just PC to PC it didn't work).
Edit: I should mention I bought Reddit Gold just for this feature, so I was optimistic that it'd work.
Nope, if you fire the AJAX request directly on the onclick event, chances are high it will not be submitted/processed before the browser navigates away...
There has to be a better way to indicate :visited, using browser chrome.
Perhaps only showing the visited info on mouseover (as a cursor style),
or limiting it to cases where the style is a color-change that is not nearly the same as the background color, in a DOM element that is front-most z-index... (but this probably can't be computed reliably...)
or just defaulting to disabling, until the user approves the domain or path (NoScript-esque)