There’s two kinds of spammers; bots and humans. You have to stop them from registering. If they sneak through, you have to stop their posts from appearing.
The most notorious bot is xRumer, the newest version of which can solve captchas, ReCaptcha, and many questions like “What color is the sky?” and “What is 12 + 6?” Stopping the bots is easy; the right kind of human verification questions. I use fill-in-the-blank style questions from popular culture, among others (“The Rolling _______”), geography questions like “Name a large city in Texas that is NOT Dallas, Houston or Austin”, and the like.
Human spammers tend to come from certain counties; India, Pakistan, Sri Lanka, and Bangladesh are the most notorious, but there’s a growing number of others like Poland, Vietnam, and Indonesia that tend to have a high ratio of spammers to legitimate users. I use a plugin that move users that register from selected countries and known proxies into a moderation queue. I’ll check the queue daily. The spammers are easy to pick out; inconsistent information (location in “US newyark”, IP in India), butchered Anglo names (“Smith Robbert”), usernames that show up as a new user on hundreds of other boards, and so on.
I also use the Stop Forum Spam plugin, that compares the IPs of new users with a regularly updated database of known forum spammers. This catches most bots, and many humans. I also have a blacklist of keywords commonly found in spammer usernames and email addresses, trouble-prone free email domains (mail.ru, potcha.ru, 126.com, etc), and disposable email addresses (mailinator.com, etc.).
For those that get through, usually from a Web host in the US, Canada or western Europe that’s being used as a proxy, I use a plugin that moderates posts that contains URLs or certain keywords from new users.
I have even more spam prevention measures, but I’m reluctant to reveal them here. What I described above will stop most forum spammers on a vBulletin site, though.