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. 

 Actually that may not work because then you'd have to pay multiple times to send to several relays