I think the privacypass type solution (of which cashu is a variant) is probably the best fit here, and if captcha isn't the best way to pay for those blinded tokens, long term (and surely it isn't), we could go the route of utxo ownership proofs of the type I'm working on (directly paying on LN is possible,  but suboptimal for privacy).

PoW to me only really fits the bitcoin use case, the problem for more consumer type applications is that the honest user only has advantage over the kind of attacker who needs literally millions of accounts. The cost to the honest user is not negligible enough, I feel. But it's a debatable point. 

 >utxo ownership proofs

feels limiting, most people aren't likely to own utxos in the first place  

 Good point for this use case.