I linked to http://en.wikipedia.org/wiki/Reykjavík and followed the link. The CSS link :visited did not style correctly. It does on the other links, but not this one or others with non-ascii chars. Characters such as the í are confusing the history to thinking they were not visited.
Confirmed with a local debug build of WebKit r28968 with Safari 3.0.4 (523.12.2) on Mac OS X 10.4.11 (8S165). Works with Firefox 2.0.0.11.
See also: <rdar://problem/3557378> (visible to Apple employees only).
This seems OK now. Can you confirm?
I can still reproduce this with Mac port.
Can reproduce this on Gtk port, doesn't occur on Chromium. Given the following two links, <a href="Reykjav%C3%ADk.html">Link #1</a> <a href="Reykjavík.html">Link #2</a> on Gtk (and I suppose Mac as well) clicking on either link #1 or link #2 only marks link #1 as visited. Chromium marks both links as visited when either of the two is clicked.