I've suffered from the same malware issue earlier. Since we use ad networks for advertising it works as follows. 1 ad network has about 3000 different ads running in different locations. If any of those domains get compromised and blacklisted and Google notices that you served something from that domain - BOOM! You're on stopbadware.org and need to get your website reviewed. You block the ad, and apply for a review. To their credit, it takes about 24 hours for the whole process (review happens, they delist you, Google caches update, etc.). However, for 24 hours anyone who comes to your site or clicks on a google result for you, or clicks anywhere to come to you - Gets a massive warning. The cost in terms of lost revenue and reputation damage are almost incalculable. This has happened to me in the past, several times. I have severed relationships with several ad networks and yet this keeps happening - even with the most reputable networks and you try to stay ahead of the curve but if you fall behind even a bit, you may get blacklisted again. All this for a site that makes maybe $200/month.
Another problem I faced was with SURBL. It's a spam blacklist that works on a bizarre system. Basically if they find your domain name beind spammed around the internet (it could be anyone else doing it) they will blacklist you. What's worse is that providers like bitly, facebook, etc. use the SURBL blacklist. So what happens ? Well, one day someone goes and spams your domain on internet forums, etc. SURBL picks up on it. Then, suddenly all your facebook links, bitly links shared on twitter, etc. start showing warning pages. Basically someone clicks on your link on facebook and gets a page saying "This site may harm your computer". Ditto for Bitly as well.
I tried to get delisted but no one at SURBL would respond. I kept trying to get in touch through their online form but no one responded for 2-3 weeks. Finally, I did a whois on the domain, found the admin contact and emailed him. I also sent him a text on his phone. At last after about 4 weeks of being on SURBL I managed to get delisted.
That. Was. An. Ordeal.
This in my opinion is absolutely unacceptable. Spam blacklists do have a responsibility to be correct in their assessments. And if they do have a false positive for any reason, they should have a streamlined resolution process. Unfortunately, the internet is the wild west and shooting before asking questions appears to be quite acceptable in these parts. I recognize that a lot of this is an attempt to protect users but when I open my mom's PC, I still see a bunch of browser toolbars, bookmarking widgets, etc. etc. (malware, right ?) Folks are still getting phished. This fight needs to be rethought.