IP blocks; block known spammy strings; bayes spam filters, require PoW, require payment, whitelist pubkeys and their follows, and aggressive rate limiting... or some combo of all the above.