The thing is, we have a way to stop this right now. We have this https://github.com/nostr-protocol/nips/blob/master/13.md

All a relay really needs to do is set some small difficulty threshold and the problem is solved. Some guy can throw a couple bots up or whatever, but this mass spamming from newly generated accounts goes away.

It would also be interesting if we could attach PoW to our kind 0.