If you don't want to annoy your visitors you're going to need to have the max runtime on any device at around 25 seconds.
Now you can't scale this per device, because you can't rule out devices spoofing what they are. So this means you're looking at barely a few seconds to break it on any sort of desktop hardware, and even less on any dedicated server.
Spammers are probably waiting longer than that to just load the page they want to spam, so it wont slow them down. For this to work you need to solve this issue, and I hope you can, but I don't see how.
Regarding feasibility & cost, what do you think of the old '"Proof-of-Work" Proves Not to Work' paper? [1] From what I remember, the time to hash adequately would be too long to be of practical use/benefit.
And you remove CAPTCHA :)
That means that even if you scale the work to take at most 10 seconds on the client machine, you'll be able to crack 1/s on a $5/mo on digitalocean. That's ~2.6M answers a month. That's $0.002 per 1000 captchas, instead of $0.70 mentioned on the website and as a bonus it removes the part where you rely on people who could mistype things.
I really want it to work, but does the economic balance actually work here against the spammers or for them?