Blacklisting is useless, spammers can keep making new accounts. Paid relays will make it more expensive.
Discussion
Spammers can also join paid relays. Paid relays add spam resistance. My thinking is more of paid relay with a referral system. Paid keeps the lights on and referral gives trust of not being a spammer.