The problem is false positives. Graham's experience of combating spam involved writing a Bayesian filter for his mailbox. That's fine. Somebody misses a message and one of the two parties feels bad, but they eventually either catch up or get over it. You can't "leave" that platform.
Twitter, on the other hand, is pretty sensitive to false positives, and the vernacular is so unique that naive Bayesian filtering would destroy a lot of communities with their own vocabularies and languages. If messages start arbitrarily dropping on it, its users won't stick around.
Sure, you could absolutely knock out spam. It wouldn't be that hard. Because fighting spam isn't the hard part. It's dodging the problem of firing on innocent people that the spam is using as body shields that's the hard part.
They already get incredible volumes of criticism for what little false positives they already have. Imagine if it was normal to be put in a time-out box by a Bayesian filter that wasn't tailored for your community!
Combating spam is something that has very few possible upsides for twitter, and a catastrophic failure case. Right now, spam mostly tends to effect larger accounts, who are going to stay on the platform anyway, because it's where the people are. What little spam small accounts see is manageable, and they won't leave because of it because it's so insignificant. If suddenly they couldn't send messages to others at random and without warning? Why would they stick around, then?