Wouldn't some sort of proof of work be a good solution to the captcha problem?
Specially since all of the sudden, a bot service running hundreds of thousands of requests will suddenly and inadvertedly have to compute cryptographic hashes at the cost of the user running the bots?