Lesson to use an intrusion detection system like Aide or Tripwire. Personally I use Aide, and I also keep it's db checksum independently (the script mails it to me on each build) so I can check if Aide itself has been compromised.

This alone can prevent such problems in the future as the system will (should, at least) show all the files that have changed and should not have. Naturally, those files that SHOULD change, like logs etc..., shouldn't be covered by Aide. But at least it can cover the most important ones like /bin, /sbin, /usr/sbin, /etc and perhaps some files in /var (like package manager's). Update Aide DB on each system update, program (de)installation or config change.