With a PoW captcha, it doesn't matter how smart you make your algorithm, it's still going to be slow. With existing systems I'd argue it's probably a lot slower for people than for machines, especially since it's people guessing what a machine thinks people would classify an image as.
This is an easy solution for rate limiting low trust/high risk connections and better software isn't going to magically make it any faster. This has always been what captchas aim to accomplish.
Hell, charge me one penny per refresh and a dime per tweet and login attempt. Then let the bots run freely if they're willing to pay that rate.
Seems like this might exclude users lower-end electronics that might be low-income.
You can have it turn itself off during a normal "1 request per minute" day on a small blog and then crank up to "A new CPU needs 2 seconds" during a DDOS.
Use token bucket or leaky bucket or whatever so a few normal users clicking around for 10 minutes won't trigger it, but after a while the server runs out of patience if they keep making requests faster.