Re: Looking at the problem backwards
Ensure the code for the adverts is sent to the publisher to be published. They can then automate the screening of the code for re-directions (and embedded malware).
I was thinking of something like this myself. Recently I was bemoaning how Flash became such a cesspit because it allowed arbitrary code to be run, and how a more declarative programming language would have solved all the problems. That approach could still be the answer to the problem of "malvertisement". There would be sections for all the graphics "assets" and some basic scripting language that allowed for interactivity. In fact, SVG + this new scripting language would fit the bill nicely.
The language spec and interpreter would have to be designed so that it was impossible to, eg, smash the stack or call itself recursively. As for redirects to an external website, these would have to be declared in a static part of the SVG file, so there would be no chance to modify them or obfuscate them. No other external assets would be loadable from the ad itself.
Providing there's no underlying bug in the SVG or interpreter for the scripting language, then at least the ad itself would be easily vetted (both by the site that will embed the ad and the user who is being asked to view them). What happens after the redirect is, unfortunately, still beyond the control of the person showing the ad (if there is malware hosted there, it can be sensitive to context such as the HTTP referrer field or cookies stored on the viewer's machine) but at least the ad itself would be safe so long as nobody clicked through, and other means (such as black/whitelisting or some sort of trust rating) could be used to give some assurance that the target site won't be hosting malware.
No re-directions, no malware