Need to be smarter than captcha
Given that Indian/Russian sweatshop workers will undertake human-powered captcha bypassing for a few dollars a day, what's necessary is a raft of tests assigning a score for each, like the better spam filters do, a sign-up failing to achieve the necessary score gets dropped.
I use a set of 12 tests (currently) like this on form-to-mail scripts with great effect.
Regularly changing the algorithms can help too. I switched a relatively unprotected page that was getting abused to use heavyweight validation. Those that marginally fail validation get a "not sent, looks like spam, try again" type of message - but those that fail badly get returned to home page - just like a poor form to mail implementation might do (those that get it right see a "message sent" confirmation). Because I use JS validation too it is very unlikely that genuine users will get black-holed.
The result is that the spammers don't know they failed so they stop trying to get around the validation, just keep pumping the messages through unaware that they are all getting black-holed. OK, my servers do have to deal with validating and dumping that traffic but at least the spam's not getting through and the spammers stop probing for weaknesses.
Of course where the abusers are signing up to, say, a forum it's harder/impossible to fool them to that extent.
A small credit card payment to sign-up would pass a share of the validation problem to the Banks - and encourage the Banks to tighten their card validation systems! (and at least earn some cash!).
I'd happily pay a dollar for a gmail account - in fact rather more... best not tell them though!
I guess we'll never get to a foolproof system but we can increase the cost of bypass then at least those with leading-edge validation can expect the spammers to go for easier targets in preference.