What happened to "A compromised machine can never be trusted again"?
Here's a particularly creative technique I recently came across: https://gist.github.com/dergachev/7916152
From your gist:-
ls -al /bin/nano # -rwxr-xr-x 1 root root 191976 2010-02-01 20:30 /bin/nano
chmod u+s /bin/nano # installs the backdoor
ls -al /bin/nano # -rwxr-xr-x 1 root root 191976 2010-02-01 20:30 /bin/nano
What you should see is:- # whoami
root
# ls -l /tmp/sh
-rwxr-xr-x 1 root root 109736 2014-01-16 16:20 /tmp/sh
# chmod u+s /tmp/sh
# ls -l /tmp/sh
-rwsr-xr-x 1 root root 109736 2014-01-16 16:20 /tmp/sh
# chmod u-s /tmp/sh
# ls -l /tmp/sh
-rwxr-xr-x 1 root root 109736 2014-01-16 16:20 /tmp/sh
If you've got 'ls --color' then you'll see the filename is different when setuid (white text on red background rather than light green on default background - if colours are the default).Not saying it's impossible to do a full clean, but I would certainly not trust a server once compromised.
So, power down, boot from a clean medium and do a full check, validating (debsums, tripwire, rdiff with a copy of backup, etc) every configuration and executable file out there. Or, to save time, just wipe everything out and quickly redeploy the services.