Pain removing a perl rootkit

If I can give you any advice, it is to stop wasting your time cleaning up. Make an image of the OS for forensic stuff for later, and just reinstall the server.

Sorry, but its the only secure way to resolving yourself from being rootkitted.

Later you can check the image, for certain reasons, why it happened.

From my own personal experience, I did this, and later found an internal user which had a SSH key containing the flaw of openssl in 2008.

I hope, it clears up the things.

Note:
If you are going to image/backup the server before reinstalling, be very careful, how you do this. As @dfranke said, boot from a trusted medium to backup.

You shouldn't connect to other machines from a rooted server, as great rootkits are known to be able to spread through trusted sessions such as SSH.