I feel to some extent spam will have to be addressed by standard server-side rate limiting and banning of abusive IP addresses at the relay level, that at least helps keep the complexity out of the protocol itself 

 For the most part as a user I don't care about spam because I don't follow spammers. It seems like more of a problem for relays.