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?
no, because a lot of bot service run on botnets, made out of hacked regular residential computers, routers and so on. They will feel a bit more sluggish, but it won't cost the botnet authors that much more.
On the other side, an amount of work reasonable for modern desktop will absolutely overwhelm an older cell phone.
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?