Spammers wish to post links on a wiki, against the wishes of the community. They do this to increase PageRank of a particular site, but because of the way the PageRank algorithm works, need not actually post links to that site. As such, there need not be any recognisable pattern to either the URL or the name of the link (if the link is named) - a random string of characters will essentially suffice in both cases. Spam therefore cannot be distinguished from regular links.
The domain linked to will be owned by the attackers; however, domains are cheap, and thus essentially throw-away. There is a cost in time and money to get a new domain, but dozens or maybe hundreds of domains are an acceptable overhead. One cannot hope to block all, or even most, attacks merely based on the domains linked to.
Spammers can be essentially anonymous and untraceable. Dial-up accounts are again essentially throw-away, and with some initial investment of time an attacker can crack a large number of vulnerable computers to increase their IP coverage. Our attacker therefore cannot be distinguished from average Joe user based on IP or access patterns, since he has the ability and the motivation to develop resistance to any published approach.
The solution: Don't attempt to block the spam; simply make it easy-as-pie for a human to spot and do a GlobalRevert.
Because global reverts can be very a dangerous and powerful tool, you may want to consider implementing CitizenArrest instead.
A suggested approach (RecentLinks): Publish a view of RecentChanges oriented around recently-added domains; pages with no new external links need not even be displayed. Integrated into this view is a form for easy mass-reversion of changes. (Here, "easy" means marking a single checkbox for each spam page, not the traditional three-link shuffle.) Since attackers may cover their tracks by removing their own links (not knowing they are shooting themselves in the foot as history is NotIndexed), it must be easy to revert to old versions even after subsequent changes; if a page was created with links on it, it must be easy to mark it deleted.
Merging LinkVeto into this system to raise the cost of subsequent attacks even a little may be useful.
Establishing a global domain list would also make it easier to add a LinkThrottle, a useful complement to this system.