A malicious admin may potentially have installed a backdoor into the system. Short of backing up your data and moving to a new server I would not be overly confident that such a person (if determined to do harm) could be denied access.
among other things you will need to check all directories accessible from the server in which it is permissible to run scripts and all scripts within those directories. make sure you are using basic authentication for all directories that should not be public.
Your current approach is to block all holes you know of. The better approach is to close the server and only open the holes you need:
1) Stopping all network services which you don't need. Create a list with netstat -nlp and see which programs are listening to ports. Only leave those which are necessary to run your system.
2) Use a firewall (hardware or software) to block all access to the server, and only open ports and IP addresses you want to be open. If you are the only one with SSH or FTP access, then only open these ports for the IP address of your own computer.
3) Use the hosts.allow and hosts.deny files (TCP wrappers) as an extra layer to control who has access to specific services. I once had a setup where the firewall didn't start automatically due to a configuration error and passed all traffic unfiltered to the server. The extra security layer of TCP wrappers kept my server secure while I fixed the issue.
4) Check all scripts if there is a way to execute system commands via a web interface.
5) Check the set-root bit on all programs to see if someone may have added that to a command to gain root access without the root password.
6) Check the crontab and at queue to see if some processes are running periodically which might give access to others.
7) If you had some really savvy people on your server, the best option is to rebuild the server from scratch.