This happened to me once, too. Russians used a hidden back door in a very popular piece of forum software I was running to plant their nefarious payload. I eventually found the security hole (the company used it for "maintenance" and has since removed it from current versions of the software) and fixed it, but by then the damage was done. My site went from 50,000 uniques per day to 2,000.
I limped along like that for quite a while, and couldn't figure out why Google wasn't removing the flag. I did everything I could -- filed online appeals through Webmaster Tools, moved the whole site to a new domain, even a new host. Nothing worked.
Eventually I found out the problem -- There was a SECOND payload hidden in the site. Either the first people who hit the backdoor planted two malware services in the server, or two different groups did. I thought I'd caught everything getting rid of the first infection, and thought Google was seeing ghosts. But it turned out that it was a super-stealthy, very clever piece of code hiding in there that continued to cause the positive malware reports.
I eventually got rid of it, and the site has a clean bill of health from Google now. But the road to recovery has been very long and slow, and that site is still only at about half of the traffic it once had.
Moral of the story: In spite of what you think, Google's false positives may not be so false after all.