If it had been done for more nefarious purposes, wouldn't "they" have been more discreet, carefully wiping traces of their activity from the logs? Not doing something that immediately throws red flags like sending thousands of email messages?
In all honesty, I certainly don't have the skills to detect an NSA-level attack that doesn't involve brute-force attempts on accounts. I can erase or alter logs, but then there are logs logged of me vi'ing logs, so I erase the shell history, but then that gets logged when I log out. It's a weird loop I don't know how to defeat, but some people do.
The heart of our problem was a misconfigured sshd that permitted remote logins (not root logins) on all user accounts. A disaster in the making. We got lucky that it was a spammer who compromised the system and not a competitor.