Ideally you'd have something that's hard for the client but easy for the server to verify, though. so maybe prime factoring?

Or, the server provides a random string of bits with length n and requires a string of bits with length n+m that starts with the provided n bits and whose SHA-1 hash begins with 20 zero bits.

What nonceness!

Imagine when a miner is used as Captcha and would only pass when a certain amount has been mined..

Spammers use botnets, so they have plenty of computation available

And if every site does this, they have plenty less. Imagine if you can only attempt your spam 20 times per second instead of 20000