It's probably a typo (or copy-and-paste-o) but if your ls -l of the binary with setuid is showing "-rwxr-xr-x" then you're more than likely running a rootkit version of ls that hides setuid info.
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).They have a link scanner which I've actually used before which is good, but I doubt I'm the target audience in terms of paying someone for a cleanup. Perhaps different parts of the company are at a different level.
Here's a particularly creative technique I recently came across: https://gist.github.com/dergachev/7916152