Stop Badware needs a serious overhaul. At the very least, they should contact the contacts in the WHOIS record for the domain BEFORE doing anything.
Why? This isn't a responsible disclosure, "we found a potential vulnerability but we don't know if it's being exploited yet" kind of situation. This is a "there's a real threat to anyone visiting that site via your search engine right now" kind of situation.
As a user, I'd be much happier if the search engine flagged this immediately.
As a site owner, if someone found malware on my site I'd want to know ASAP too. Obviously it would be helpful if they sent me a notification and made the specific details of the identified threat available. However, I could hardly criticise them for blacklisting my site while it should be blacklisted, or for claiming that we were dangerous while we were actually serving malware.
Not clearing up the blacklists promptly after the threat is identified and removed is an entirely different question. If you're going to go around blacklisting sites then I think you also have a responsibility (and, for that matter, you should also have a legal obligation) to remove them from the blacklist with similar efficiency if you're notified that the threat has been removed. Claiming that someone's site is dangerous when it isn't is defamatory, and should be treated as such.