Because of the nature of Wikipedia, articles tend to get rather congested with links. All these super-bright reds and blues and gaudy underlines can sometimes get the better of an article. I was working on [[w:LAMP]] just now when my eyes just couldn't take anymore.
Are you aware of the user preference "Underline links"? I think that making non-underlined links the default as well would be nicer; the argument that they are no longer recognizable as links doesn't count, as the colors are sufficiently distinct. Underlining is generally recognized as the most distracting of all styles in typesetting, which is why it is almost never used in print.
There is one advantage to underlining on Wikipedia: If you have two links right next to each other:
[[December 7]] [[1981]]
These get underlined separately, whereas with no underlining you cannot tell whether this is one link or two links without hovering.
It might be nice to find some softer colors for links, visited links, and non-existent links.
It's not as bad if you turn underlining off, but I agree the colors could be nicer. On the infoAnarchy wiki I use red on a slightly gray background for non-existent pages:
http://www.infoanarchy.org/wiki/
(I also use underlining there, but mostly out of laziness.)
Regards,
Erik