I agree that nuking entire domains would be bad for the Internet Archive. But I don't think it would be overwhelmingly difficult, nor controversial, to identify and remove the vast majority of "contaminated" documents. This applies to the Internet Archive as well as major search engines.
First, we're talking about raw memory pages, not merely malformed HTML. Those memory pages might contain valid HTML, but most of the sensitive information is in the headers, not HTML markup. It won't be very difficult to write a script to identify documents where random headers and POST data have been inserted where they don't belong, or where the markup is so obviously invalid (even compared to similar documents from the same site) that there is a high probability of contamination. Having a full list of contaminated domains would obviously help a lot, because we'll only have to deal with thousands of domains instead of millions.
Second, contaminated documents by definition contain information that is NOT what the publisher intended to be crawled, indexed, or archived. So there should be less resistance to removing them.
Finally, most of the contaminated domains used features such as Scrape Shield that were intended to deter archival. It's as if the domain had a robots.txt that said "User-agent:* Disallow:/". I'm not sure whether it's even possible for the Internet Archive to archive such domains. If they can, maybe they've been doing it against the publisher's wishes. If they can't, well, there's no problem to begin with.