Du kan använda
http://www.stopforumspam.com/s API för att kolla om IP adresserna är dokumenterade spammare.
Sedan kan du ju tvinga folk att verifiera sig när de skapar ett konto, till exempel be dem addera 5+4.
Jag föreslår att du skippar Captcha, eftersom det är så otroligt jobbigt och de flesta användarna hatar det.