Hosting Acct Hacked and Deactivated

I'm not sure if this is the right place to post this...but anyway:

I received an e-mail from Bluehost this morning that my account had been deactivated for a TOS violation. I contacted them and they said that at least one of my domains had been hacked and had malicious files, causing the IP to be blacklisted by Spamhaus.

I called support and they told me which file caused it, and also ran a malware scan that revealed other files that needed to be deleted, which they provided me a list of. They also said I needed to purchase a dedicated IP, and after all this was accomplished I could call back to be reactivated.

So I did this and when I called back they said they couldn't reactivate because there were still harmful files. Basically they told me it was my responsibility to identify and delete all such files before my service would be returned. I asked if there was a software and they said my only option was to pay for a service like SiteLock or We Watch Your Website to do it for me.

Has anyone else had anything like this happen? And if so, what are my options? I cringe at the thought of paying MORE money per year for each site. Half of them aren't even making any money, and the other half don't make enough to cover if I have to keep buying services for them.

Please help,
Chad

UPDATE:
Did some cleaning up of my own, bought Sitelock through Bluehost, and just got re-activated. Hope it sticks.