Since making relevant PoW for each note is annoying and somewhat broken, another option that came to my mind was a relay that required PoW on pubkeys instead of on event ids.

But since your pubkey is something you create only once this is a super inflexible scheme and annoying. But then I realized we could define a new event, say kind:13000, which would be just a replaceable PoW for a pubkey.

Then we could have a relay that has difficulty adjustment for the amount of PoW they require in such event, and pubkeys can upgrade their PoW as the time passes. Or relays can require a certain amount of PoW, but from a recent event, to force users to redo their PoW every now and then, and other variants of this.

This all in the context of "beginner" relays. Once you're a established Nostr accounts with followers and activity then other relays will start to open up for you more naturally without requiring PoW.