The one with the biggest effect and one of the simplest techniques is to relocate and rename your registration pages. We have it set to scirra.com/register but we get loads of 404 requests to scirra.com/forum/register.asp and scirra.com/phpbb3/register.php etc. Move it somewhere else and rename it, a majority of scripts will 404 and move on. This is pretty much blocking 90%+ of all spam signups.
Secondly, we have honey pots set up as well. If you view the source of the registration page you will see that there is a username field, but this is a hidden field. The actual username field is called something obscure. If the username field has a value when it is submitted, it will reject the registration. No real registration will ever fill a 'username' field out with a value, so if it has a value we know it's probably a bot. This seems to catch out a few spammers a day as well.
Lastly, a great bunch of moderators also really helps as well as a community who are able and willing to report spam posts :)
We still do suffer from spammers, but the spammers using automated tools (like the one beginning with xru...) are pretty effectively blocked. There's also literally nothing you can do about paid human spammers except manually nuke the user when you come across them. Labour in some countries is extremely cheap and this becomes +EV to hire if your running a spam operation sometimes.
Spammers are a royal PITA for web developers. Interestingly, when we have been forum spammed I've actually contacted a few of the websites the spammer is promoting. What I often find is that the website is *sometimes* oblivious to the fact their website is being spammed (other times they feign ignorance). They think they are paying an 'expert in SEO' to help their website rankings, but all they have managed to hire at the end of the day is another knuckle dragging spammer who litters the web with dirt that honest webmasters have to spend hours a week cleaning up! It's very frustrating, but it's something you have to accept and account for when running a website nowadays.
For a site which is the size of ours, we probably have to ban around 1 user a day now on average. This is completely manageable. Without some of those techniques described above you would probably be looking at around 20+ accounts per day. I'm fairly sure a lot of the ones we do ban are human spam accounts.
The techniques above as well are easily circumnavigated. However, it is not in the spammers interest to beat our system. If they do get through, we deal with the swiftly. Because we have taken these measures as well it would suggest to the spammers even if they did beat our system ours would not be a site worth spamming as the likelihood is we care about spam and would remove it quickly. There's much softer, juicier targets out there. A lot of spam prevention is just staying ahead of the pack in my opinion for this reason.
I could write a short book on SEO 'experts' and the scams like this people run. Unless you really really (really) know what you are paying for, don't pay for SEO. For all you know they could be spamming on sites like this as part of their service.
If spam is still a problem after all this we have looked at using a service such as Akismet. It's got an apparently amazingly low false positive rate and comes at high recommendation from many sources. We haven't needed to use it yet, but we will if we need to.
In regards to CAPTCHAS I want to avoid them. They are very inaccessible (which I care about) and I'm very certain they deter people from following through with signing up. Personally I've been on websites and had a CAPTCHA, got it wrong and the form was handled badly and asked me to re-enter a lot of fields. Sometimes you get stuck in a washing mashine of re-entering fields and CAPTCHAS and at the end of the day who can be bothered to do that? Best to not lose sign ups if possible. One way to do that is by not using a CAPTCHA.