Step one is to see if someone's spamming from your server.
First go through your mail logs! I'm used to exim, but I'm sure the steps are the same. Look in your mail queue, and see if there are any messages queued. A large spam run will always leave you with messages that can't be delivered for days at a time, because spam mailing lists always have invalid entries.
Also parse the mail logs. For exim I use grep '<=' /var/log/exim_mainlog | awk '{print $5}' | grep \@ | sort | uniq -c | sort -nk1 to see how many messages various people have been sending.
Lastly, check the headers in the bounce messages to see if the mail is actually coming from one of your machines/instances. You could just need SPF records.
Chances are by now you'll have a good idea whether or not your server is hemorrhaging mail everywhere.
If you've found spam messages, try to see what mail user they're being sent as. Change that user's password. Usually random spam comes from php scripts, php usually includes an X-Script-Sentby: (or something) header in the messages full headers, that you can use to find the responsible script.
Most of the time you'll find some random php script that fires mail everywhere. Occasionally I see people spamming through horde (which is a little harder to track) or outlook or using other clients that just require a password.
If mail is coming from your server and you're not sure where, you can also put disable_function=mail in your php.ini
Being rooted is the least likely scenario, more likely is some random php application got hacked. If you did get rooted try rkhunter or something, also hackers tend to use bizarre names for script, and php scripts left by hackers tend to be eval(base64_decode(gunzip( compressed, so if you grep -r eval $docroot you can usually find malicious scripts. Lastly, clamav isn't too bad at picking up malicious php hacking scripts.
grep nmap /home/*/.bash_history
and tightening my iptables to my list of things to do on my new server.