What I'm always paranoid about is that I work in a community of security researchers that sit on and occasionally drop 0-days: I have very little trust that much software is actually remotely "secure". Meanwhile, the only reason I had noticed those other attacks is just how sloppy they were... a more targeted-to-me run by a more careful attacker would have maybe never been noticed.
It has drastically changed the way I think about security, FWIW; as one example: I don't every store logs on a box being logged anymore. Instead, logs are immediately transported to another machine whose only purpose is to accept and store logs (and so is listening for incoming log packets, OpenSSH, and nothing else. The first thing anyone does is attempt to patch themselves out of logs (one attack I noticed because wtmp was mysteriously damaged).
Hacked versions of common utilities is a common payload for rootkits.
You should still run the scans, just be aware of the limitations.
Once you've lost root to a sufficiently competent attacker you can't trust _anything_ on that box any more.
One thing that'll help against (some) script kiddies with rootkits is to have available statically linked copies of every tool you might want to use to see what's happening on your box - for a long while, every colo-ed box I managed had a cdrom drive with read-only versions of /bin, /sbin, and useful bits of /usr - all with the binaries statically linked. They can in handy a few times (mostly to confirm that "yep, we're screwed. Get this box off the network and powered down immediately and implement the bring-up-a-new-server-from-scratch plan right now".
At some stage though, you can't trust the kernel or the hardware - an attacker who's got into your booted kernel or your bios or your network card firmware, if they're good enough, they probably can't be detected by examining anything you could see logged into the box itself. The only way to identify that level of attack is by monitoring the traffic from the box from some trusted piece of network gear upstream of your rooted server (and against a sufficiently talented attacker, even identifying unexpected outbound traffic might be impossible. If your list of likely attackers includes three letter agencies or nation states, I hope your getting your secutiry advice from somethere other than HN comments…)
Nobody should lose any sleep about BIOS embedding and similar - that level of attacker and sponsor imply a level of threat that no typical organization has a chance against.
In my opinion, after years of pondering dozens of intrusions with many types of ways in and regular failure of all kinds of defenses I don't think there is much advice to give aside from the flaw is in your custom software, stupid.
I have become a really big advocate of CM and push button provisioning with identical replacement hosts that build from scratch and commonly get refreshed - relying on code and configurations managed centrally.
The best way to remove an attacker is a complete rebuild. If you're already using Chef etc why not just dump them proactively? Some roles don't lend themselves to this, but I assure you it is like a massive weight has been lifted.
So this happened to me once, but it wasn't ps or netstat but sshd that had been replaced. We only noticed it because the replacement sshd was bad and didn't set up the PATH correctly so "darcs push" stopped working (it was presumably set up for a different linux distro than we were running).
If one has root and patience - flash BIOS and wait for a coldboot. One can even get an IP stack to pull down new firmware between boots. The user sees a normal post screen and your hypervisor sees normal hardware adapters.
See Jonathan Brossard's 'prior work' slide from his Defcon talk on his work [1] for more details on the state of X86 backdooring.
'Trusted computing' and all that.
[1] http://www.youtube.com/watch?v=yRxDvkKBMTc
https://media.defcon.org/dc-20/presentations/Brossard/DEFCON...