Sounds like you're talking about rootkits, trojans and worms - not viruses (since this appears to be a Linux server not a MSWindows box).
ClamAV is an anti-virus tool while it does go some way to detecting other types of malware it's abilities are very limited. Indeed, unless your are running samba on the server (which would be a really dumb thing to do) or are allowing anyone to upload files (again, dumb) there's no point in using ClamAV.
The first thing to do is to get the server wiped clean and reinstalled from source media. Then follow the usual steps in re-instating the services (i.e. make sure you're not installing the same backdoors from your backups).
I'd recommend getting some competent help to harden the server - it shouldn't take more than about a day to get the system relatively secure (assuming you've already ensured that anything you've restored from backup is safe). Part of this will include locking down any remote admin access, particularly via ssh.
You should also instigate regular backups and runs of rkhunter / chkrootkit.