I'm an admin at another board, and I've been very successful at keeping out spammers. I have these lines of defense:
A captcha: reCAPTCHA
A challenge question. I installed "NoSpam!", a vBulletin add-on that implements challenge questions. I use simple ones, like
2 plus 3 equals
Putting new members into a moderation queue so I can check them out before admitting them.
A geolocator for IP addresses. I've found this one to be very reliable: http://whatismyipaddress.com/ip-lookup
Sites that list known spammers. My favorite is http://www.stopforumspam.com
though I've used http://www.botscout.com
IP banning. I mostly use that for spammers coming from a certain place.
I also log every spammer that tries to register, so I can look for repeat cases and patterns.