[jfengel]

Blockchain, perhaps?

A lot of CAPTCHAs protect things that are very cheap, but where they don't want it to be free. One solution would be to charge money, but people concerned about privacy won't want to give away conventional payment information.

So, perhaps a nominal payment in some reasonably anonymous cryptocurrency? Or even just participating in some proof-of-work problem that would cost a few cents worth of electricity?

That wouldn't stop really serious botnets or people with stolen credit cards, but those are also both illegal and should be shut down for other reasons.