It allows for unlimited tries. Let's say current ML system could solve 1% of the captchas, then an attacker could try a million captchas and generate privacy passes for equivalent of 10k captchas.

Theoretically, to penalize the user you need to identify the user. And for that you need to maintain long term identity.

You still wouldn't need that.

Trivial counter-examples include proof-of-work (see HashCash) or cryptocurrency micropayments (not necessarily settled on-chain, so transaction fees are not an issue for the user).