On his blog Arve Bersvendsen talks about a comment spam solution he wants to implement in his own blogware. I think the approach shows promise and maybe it's something that WP could benefit from.
1) comments by unapproved commenters will be presented on the weblog stripped of all URLs, even plain text (not linked) URLs in the message body.
2) links/URLs will be restored in the comment when a commenter is approved (as being a proper, responsible, human commenter)
3) approval of a commenter, in Arve's proposal, can be done by a moderator or by gaining a minimum number of votes from already approved commenters.
I'm not a coder, but I can see this work with WP. There already is a permission based user registration, so what is needed is making use of that system to define the different commenter roles and some code to strip any form of a link from a comment upon presentation.