Even if you reduced the proof of work from 30 seconds to two seconds, that's negligible to the user when submitting a form, but limits a computer to performing a mere 42,200 signups per day, which is several orders of magnitude better than the 1.6 million figure above.
And nothing says you can't also implement rate limiting per IP, which is frankly not terribly useful when facing botnets.
Most generic spammers (wordpress/mediawiki pharma spammers) post 1-100 messages and then move on to the next site. If someone wanted to specifically target your site, they would use a botnet or write a GPU proof-of-work solver.
You're also right about IP rate limiting not being useful against botnets, but neither is this. For pretty much the same exact reason. Each machine in a botnet comes with a unique IP address, but also 2 or more CPU cores.
Just use a CAPTCHA. CAPTCHAs aren't the problem. The way we use them is. Don't show CAPTCHAs to every user. Ask some questions first. Is there something unusual about this user? Is there something unusual about the user's browser? Location? Is the user doing something unusual? Show them a CAPTCHA. Those "surprise" CAPTCHAs are less annoying to the real user and more frustrating to the spammer, since unpredictable behaviour makes testing their scripts harder. There's a reason why Facebook and Google do this.
A much more exciting development in the field of bot/spam detection is verifying the integrity of the user's browser by comparing the exposed functionality (HTML5 and JS) and quirks to the ones expected for its user-agent header. I believe this is the method that Dan Kaminsky's "White Ops" startup uses.