I worked on root kit hunter at sourceforge.net for a while. There are similar capabilities in the scripts in that app as well.

You may be missing something essential - as an example:
root kits may change a lot of utilities in /usr/bin to avoid detection. md5sum is one of them. It "knows" how to report the old value for a given system file, even though the file is now completely different. The same is true for ls, find and so on. If you ldd those files and ldd is not corrupt you may see odd libraries linked into them.

I would:
create a separate hidden tree of ls, find, md5sum, etc. that your script points to with it's own version of PATH. Populate the directory with known good versions of the files. If you're even a little more paranoid, consider rebuilding & linking those files statically which eliminates shared library masquerading.

It all depends on your level of exposure - if you're inside a good firewall, my suggestions may be overkill.