The idea was to prove that a token exists without disclosing the token itself, nor any sort of 1:1 substitution.
That sort of thing is definitely possible, that's not the conundrum. What they said is one of the conundrums I have to admit. If the server doesn't know who the user is, then the server doesn't know it's a valid user vs a bot.
But I only agree it's a problem. I don't agree it's a problem without a solution.
One far-fetched idea is to use ZKP proofs to prove that you were verified, without disclosing anything your identity. But that's likely overkill.
Anyway, I think Cloudflare already works on something better with turnstile, the "privacy preserving captcha" and private access tokens [0].
[0] https://blog.cloudflare.com/turnstile-private-captcha-altern...
Theoretically, to penalize the user you need to identify the user. And for that you need to maintain long term identity.
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).