Re the command history, is there any way around them wiping it - e.g. piping all .bash_history entries to an append-only store?
You can also use a global bash configuration that would log all commands [1] entered into any bash shell to a central log, which could be shipped off-server simultaneously.
[0]: http://rkhunter.sourceforge.net
[1]: http://askubuntu.com/questions/93566/how-to-log-all-bash-com...
However, rkhunter has additional logic to specifically seek out rootkits and malware-like behavior, and is more specifically targeted to system file modifications. Combining it with unhide (to compare actual processes running with those visible from userspace) provides a reasonable assurance that nothing nefarious is going on.
They're all part of a spectrum, however. I use scanners like aide alongside rkhunter as well, but I'm the sort of guy that will spend a day tuning the config of aide to avoid constant false alarms.
command history is also easy to alter if you know what you are doing.