The recaptcha option is the industry standard option at this point.
Have you also enabled require_validation in config.inc.php?
That provides another hoop to jump through for registration.
I don’t have any personal experience with the Stop Forum Spam dataservice. You should read the FAQ on their site to evaluate some of the positives and negatives: http://www.stopforumspam.com/faq