Implementing a simple rule of "no links allowed for freshly registered users until "x" number of posts" would've decreased this spam by a huge degree...
As long as your "x" = infinity. For any non-infinite value of x, the spammers will just put up x posts full of non-link garbage, and then start posting link spam again. So we would be exactly where we are now, except the mods would have to get rid of x additional
posts from each spammer. And if the probation is time-based, the spammers will plant an initial post and then return x days later to do their spamming. Both of these points came up earlier in this very thread. I don't see any way to implement this solution without requiring new posters to request permission to link and for the mods to manually approve it. That could create a burden for the mods, but the Cap'n at least didn't think so
The spammers can still theoretically put links in text form (non-clickable, with spaces between characters), but that will greatly reduce any chance that someone will actually follow those links and most likely decrease the willingness of spammers to use these particular forums.
The whole point
of this spam is SEO -- they're not relying on dumb humans clicking the links, they're relying on dumb spiders indexing them and raising the linked site in various search/legitimacy rankings. So links as text have no value, which is why stripping the url tags out would be sufficient. However, for the reasons I mentioned above, I think it would be better if the post was un-submit-able if it included links and you didn't have linking permission.
Also, the Captcha for new users should be more than "see those letters, now copy them into textbox below" - any illiterate person can learn to overcome this, so can some bot programs. Instead, it should be a simple question (which would randomly change) where someone has to type in a simple non-numerical answer in English, which should discourage the illiterate spammers from foreign countries. Those 2 simple things should do it... Unless, of course, the moderators still "enjoy" manually cleaning up dozens of spam posts in various threads
There's a whole CAPTCHA industry, and a corresponding counter-CAPTCHA industry. I'm not going to presume to know what would work at this point, especially given the tight trade-offs between driving away new users (not all of whom have English as a first language) with high barriers and driving away the rest of us with excessive spam.
The sad reality is that no two things, simple or not, is going to just "do it." There's an arms race here, and unless the financial incentives on the other side change, that's never going to end. The job of the good guys is to do what they can without driving legitmate users away through sheer inconvenience (and without driving themselves crazy in the process).