Yeah, invite code to paid relay would be one simple solution to newbie-friendly spam prevention. This is not limiting anyone's freedom: users can always choose what clients and relays they use. What works best will be most popular. 

 Paying the fee is hard unless you're already a keen Bitcoiner, and are also quite sure Nostr is for you without having seen it.

The invites is workable, but still, what about the "walk-ins" who read something about Nostr and decided to come check it out? Who are probably the majority of new users... 

 I suppose in this scenario (I'm not saying it will or should happen btw) the article the person would have read would also mention this invite codes mechanism. Not sure how that would work but um yeah lol. They would still need to go somewhere for an invite code. Or use a pow service like special purpose version of a pow posting service like getwired.app to ask for one?
¯⁠\⁠_⁠(⁠ツ⁠)⁠_⁠/⁠¯ 

 I feel like I'm digging a hole here lol 

 i think pow is easy to implement without significantly affecting UX.
if default difficulty is something like 10, no users are gonna notice, but spam reply bots suddenly require a lot more resources 

 yea that was also my thinking, PoW won't help for one-to-many spam (as the work can be amortized over many targeted users), but for mass DM/reply spam it might, a bit
 

 yes, and one-to-many spam is where a ‘web of trust’ can be applied without any onboarding trade-offs