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.
Add 100ms-of-2011-avg-cpu computation and tie it to the submit button (avoiding any complications interleaving with user activity). So that deals with first-order dumbbots and makes life a little harder for Javscript-executing (but still volume-based) folks. Marry to a bayesian system to handle the third-order mechanical turk-style miscreants.
Any thoughts?