The cleanest and simplest solution is to stop using free relays.

Relays that require payment will be avoided by the bad actors because it’s impractical to pay each time for an npub to have permission to post and get banned or blocked for spamming or posting harmful or illegal content.

PoW is the solution. We already have it but many refuse to use it.