Some time after I posted my previous answer, I came with this little trick which I think is more effective to handle stolen credentials (may not work for everyone):
1) Install fail2ban (if you don't have it already) to block failed login attempts from specific IP addresses.
2) Keep track (through an script) of the geo-location IPs connecting to your server. If you detect 2 different countries in less than 1 minute, lock the account and notify the user.
Locking the account will automatically block any clients trying to use that account.
This scenario have proven being effective in my case, as I don't expect my customers from being in 2 different countries in less than 1 minute (my servers are in Japan).
However if you have mail clients all over the world, I would suggest to increase the number of countries as mobile devices could potentially show such pattern if someone is at the border of two countries.
Also this technique implies you have a way to contact your customers directly (by phone or other way besides their compromised account).
This is specially good against malware which steals credentials, as I have experienced that in such cases, such malware seems to share those credentials among several infected clients (which are located all over the globe). However it won't be effective if the spam comes from a single client located in the same country as the original account owner resides.
The tracking script can be easily coded this way:
tail -n0 -F the mail.log and pass each line into an parser script which will extract IP addresses and get their location using
geoiplookup. Keep in a database (or file) with the account and last country/countries it was detected. If you are using UNIX accounts, the easier way to lock them is using:
passwd ACCOUNT -l. Don't forget to send you an email so you know about the issue.
If you don't have scripting skills, or you don't want to start from zero, let me know and I will share my script.