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.

Or require an actual CAPTCHA before posting to a relay. Maybe there's some way of providing proof of CAPTCHA too so you only have to solve it once and you can replay it on many relays.