I’m looking forward to seeing other answers to this question, but my feeling is that if you’re catching compromised mail accounts after only 40 spams have got through, you’re doing really well. I’m not sure I could detect similar abuse so quickly, and the prospect worries me.
But I’m appalled that seven sets of credentials were stolen in the past week alone.
So it seems to me that further improvement will not be in the “abnormal mail detection and removal” end of things, but in the “minimise credential theft” department.
Do you know how these clients lost control of their credentials? If you can see a common pattern, I’d start with mitigating that. If you can’t, there are solutions both technical and non-technical to help minimise credential loss.
On the technical front, requiring two-factor authentication makes tokens much harder to steal, and makes such theft much easier to detect. SMTP AUTH doesn’t lend itself well to two-factor auth, but you could wrap the SMTP channel in a VPN that does so lend itself; OpenVPN comes to mind, but it’s far from unique in that respect.
On the non-technical front, the problem here is that loss of credentials is no headache for those who are supposed to be looking after them. You could consider changing your AUP so that (a) people are clearly responsible for things done with their credentials, and (b) you make a significant charge for each piece of inappropriate mail sent with a set of credentials. This simultaneously reimburses you for the time you’re spending dealing with credential loss, and makes your clients aware that they should be looking after these credentials as well as those to their online banking, since the loss of both will cost them real money.