If they have compromised your system and gained root access, you should reinstall your server and recover from backup. Simple as that.
They could have placed a script god knows where, ps -ef and see if you see any abnormal processes, still, reinstall and recover from backup is without doubt the fastest way to recover a functional operation.
Just out of curiosity how many mails do you have in mailq?