I think very cheap paid relays are an option. The admission is like a CAPTCHA that adds considerable friction for spammers.
If we had easy to host paid relay software we could create a market to drive prices down and also lead to censorship resistance.