After about 16++ years on the Internet and having a website, I've been hacked.
What you or your hosting provider should do to is unplug from the 'net immediately. Then wipe the disks clean and reinstall everything. OS, applications, all of it. This is what you make (and test) backups for. If it's your box, it's yours to cleanup. If it's hosted, it's normally the hosting provider's responsibility.
So why the wipe and rebuild? Because your machine has almost certainly been rooted. As in root kit. Do a search, you'll find a ton of stuff on what a root kit is and what you can do about it.
The only real way out is to start over. Don't waste your time trying to get the malware off your machine; you'll never be 100% sure your machine is OK using tools to scrape the crap off it (malicious software removal indeed). Root kits are (really) good these days. Ingenious at hiding and reinstalling themselves the second you reestablish a 'net connection.
Last time I had this happen I took the precaution of just installing new hard drives so I knew it was a squeaky clean install. The FBI said they wanted the old ones, but they never actually came and got them. Turned out the culprit was a 14 year old boy in Atlanta. Daddy was rich and the feds didn't think it worth it to prosecute. They just confiscated all the kid's computers and his parents' too (cleaned out the house, the kid had five or six himself as I recall). Anyway, if you start with fresh hard drives you can be reasonably sure that your boot sector is clean, etc.
But install and update your OS (use a known safe machine to download the updates to CDROM), lock it down tight, do everything to secure it, ***before you reconnect to the 'net.*** Do *not* go back on the 'net for any reason, not even for a second, until that box is as fully secure as you can make it. Because your box is a target now; they want it back. Trust me on this.
If you don't have and use a hardware firewall, get one and use it to lock down access to the box -- so tight that you have to physically be at the keyboard to make any changes (can't do it over the 'net, not even a VPN). It won't be 100%, but the idea is to make it difficult enough that they'll go try an easier box. Security in layers and all that.
Good luck with it.