The proof of work spam protection for Nostr I envision picks up the torch where it was dropped. PoW as a means to protect the email ecosystem never latched on, a decentralized solution wasn't necessary.

A little customer side required computation that needs to run before your note is accepted by a relay. Searching a nonce to hash the note so that it falls within the relay-specific target zone.

The relay sends a random number to you, it must be contained in the note meta data and the hash of the note must have n leading zeros.

UNLESS

Your profile is verified, you are using at least x amount of paid relays,... Then the PoW requirement is dropped.

That way we could have 'global' in free relays.

Ultimately, free relays will be sending you ads in your timeline to generate income, the must fight spam hard. No ads on paid relays.