I will echo ewwhite's advice, as well as the suggestion to drop all SMTP traffic from other than your mailhost at your firewall, from Micheal Hampton.
Another suggestion is to set up a traffic snoop on your client's apps for outbound SMTP. Their web servers should not be generating mail, so if they DO, you want to see what it's about - perhaps you can glean some insight into the original source. Other things to perhaps try:
If you know your client's IP block, you can capture telnet, remote desktop (3389) and SSH traffic to the web host and filter out their IP block from the results. This should give you an idea if anyone is controlling the host other than them.
Another type of traffic to snoop is IRC, since this protocol is widely used as a command-and-control net for zombie computers. Or simply drop the IRC ports at your firewall the same way you dropped SMTP.
Another possible vector for malware is via torrents. If your client's web server is opening torrent connections, it may be in use as a torrent distribution node as well as an email spam source. If your clients haven't requested this as a supported service, you can then either drop it at the firewall, or kill the services on the host.
The ultimate solution, once you've backed up what you need to search out the takeover vector (or if there's no real push to find out what happened), you can simply kill the VM or reimage the server, and then restore the client's apps and data from a prior backup. They might have issues with this... but, it's one of the costs of running unsecured code.