I still like the idea of making a small payment to use nostr (although if it's not crypto that probably becomes painful to implement, and if it is you alienate lots of people). Easily eliminates 95% of spam and provides some type of monetary incentive to developers or relay operators.
Discussion
I think this idea was already suggested, but certain relays could charge a toll in order to post to them (but not read from them). These relays will tend to be spam-free.