Ultimately, in principal, what counts as 'spam' is a subjective judgement and should probably be treated as such.  To me, that suggests an elegant reputation system.

I'm just thinking out loud here, so take the technical feasibility with a huge grain of salt:  What if there was a mechanism for automatically muting anyone who 10% of my follows had already muted?  - and that would cascade so that if I were automatically muting someone based on 10% of my follows (or explicitly muting), that would count towards the 10% threshold for any of my followers to also automatically mute, and so on.  So, once a new spam bot popped up, it seem like it wouldn't be long at all before that spam bot was effectively eliminated for anyone with just a few follows via a cascading reputation system.  BTW, the 10% threshold is just an arbitrary example value.  Ultimately, It would probably be best to be adjustable on an individual user basis.