I have always wondered about the ability of also storing the MD5 of all the suid files on the system, and merge that in with the nightly security audit.

Although the real problem is still that of a compromised security database, I cannot think of a "real" way of protecting against that.