why "fees OR rate limiting"? I think you need both and the former is the solution for the latter (in anonymous user context).

With "fee" interpreted in the most general way possible. Any scarcity is possible. Hence things like RIDDLE/aut-ct, and indeed hence things like privacypass/cashu/any chaumian cash,lightning payments (weaker privacy but other adv.), etc. Although, in some contexts, some of those things need a kind of "bootstrap" (i.e. they might be private, but if you have to pay for them with a non-private payment the problem isn't fully solved).