How can I reduce the damage of stolen mail accounts?

Currently I’m offering some webhosting to a few advertising agencies for their premium customers. But currently I have a great problem with the E-Mail Service. In the last week, the E-Mail Accounts of about 7 companies were stolen and used to send Spam using my Mail-Server.

Well, I was able to disable the accounts, because the sender was hitting the ratio policies of my server and a lot of mails were in the mail queue. Well, about 40 Mails were actually delivered. But it was enough to get blacklisted and even one user wrote a personal mail to the abuse of the datacenter.

Currently I have no clue, what I can do to prevent Spamming from a stolen mail account. I send every outgoing mail through SA and AV, but it’s not enough. Before the user account don’t hit the ratio of 40 Mails a day or does not flood the message queue, I can’t detect the attack.

How can I detect such problems earlier?

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.

We mitigated the same issue by using an outside vendor as our e-mail gateway (in our case, Exchange Online Protection but there's many other comparable services). We then configured all our e-mail sending services to use that as the smarthost.

Now, all our outgoing messages are associated with the reputation of the external e-mail gateway. Because of that, these services do a very impressive job in detecting suspicious outgoing e-mail activity and alerting you promptly.

I'm normally a big proponent of developing our solutions in-house but e-mail is one of those things where the return on investment is truly worth it.