Spam and DoS prevention were actually the original purpose of Proof of Work. Hashcash, the first (I think) anti-spam PoW algorithm, was what Bitcoin's PoW algorithm was inspired by.

Why not something computationally expensive? Bcrypt this value 10000 times to continue

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