AG4Life - 9:10 am on Dec 21, 2010 (gmt 0)
MattCutts: "You would think, but people who don't patch their servers are often the sort that don't notice if they're not in the search results. Another problem is that site owners wouldn't know why they weren't showing up."
The problem is that these webmasters (the ones that won't notice their site has been removed from the results) won't notice the new warning either, and your average users not paying attention (which seems to be a lot these days, judging by how many people simply click "yes" to everything, including malware prompts), can ignore the warning and click on the result anyway. So nothing has been accomplished in this kind of situation.
I say just do a temporary delist straight way, send warning via WMT and/or admin email found via whois, and if the webmaster doesn't notice a severe traffic drop, then I don't think they are the kind to care about not being listed in the SERPs anyway (so everyone's happy, sort of). De-listing instantly (well, almost) removed when the site has been fixed.
As for webmasters not knowing why their site has been removed, that is a problem. Could Google do some kind of "Webmasters Tools lite" where you can get a quick diagnosis of the domain without having to have a full account? Sort of like the safe browsing diagnostic page, but easier to find (should be linked to from somewhere visible, with a link that maybe says "Webmasters: diagnose your website", and from the "why is my page not listed any more" FAQ page or something), and includes details about suspected problems on the domain (like malware infection, or suspected hacking).