One solution that we've partially implemented on this site is to rate limit certain actions. In our case, we rate limit sending private messages, since that's usually where we get the most bulk spam. The same technique could be applies to any action. Here's where we do it:
Brett: Is in my roadmap implement filters to limit user´s actions. I will check your code and, with your permission, implement it in my antispam plugin. We still need some protection against spambots.
So it looks like a good idea to never turn off the spam trottle filter.
This morning I had this same problem.
I just turned off most of the pluggins and then I was able to delete the spammers.