If the persistence mechanism wasn't there, you'd be able to detect it from the added files -- /bin/dh and ipt_ip_udp.so in your modules directory. Tools like tripwire work by hashing the files on your system so you can tell at a glance when one changes.

there's nothing to stop it hooking opendir() and friends to hide it from ls!

True, if the tool has been built with dynamic linking. Statically linking your security tools makes it a lot harder to hide your naughtyware. Depending on how deep the rabbit hole led in your infection, there are of course other things that could be done, like a malicious kernel module overriding the getdirentries(2) syscall, which would mean even more fun manually parsing the directory entries.

Then again, the best course of action is to pull that server down and build a new clean box, and do all the analysis offline. Boot from some sort of read-only media to minimize the threat, and analyze from a known good kernel, making sure to not run anything from the infected box unless you're goddamn sure what you're doing.

One could argue that network facing machines should boot from RO media anyway with data stored on NO_EXEC volumes.