Here's an idea: Force registrants to submit a computationally expensive token along with their registration form. Perhaps it's computed with javascript. Users usually spend more than 15 seconds on the form anyways, and spammers will hate to peg their hardware like that.
Any thoughts?