Offer a money-back-guarantee, no-questions-asked, on every click delivered. "Pay for only the clicks you like," Google could say.
The catch is, in response to your requests for refunds, Google will "down-weight" (or curtail altogether) your ad placements in exactly those "places" which generated unwanted clicks. If you choose to pay for no clicks, your ad soon stops running everywhere. It's in your interest to pay for the clicks that were truly valuable, so your ads continue to run in exactly the right and honest "places".
I think this cool idea but mostly serves as an inspirational model for what could be done. Most advertisers have a hard enough time getting used to the current "relevance" model at Google. Basically, this model might be too confusing for it to make sense to most Google buyers.
It's also not clear how Google and the buyer would decide which ad placements to downweight... They could choose the wrong place, and the fraudulent clicks could increase as a percentage. You'd need some method to tune the feedback. But overall, anything that "floats" the price you pay for a click by eliminating per-click minimum costs and potentially increasing the cost for more valuable clicks could be an interesting experiment!
I also think Gordon has a very valid point: "Google is uniquely positioned to implement and benefit from such a policy." In other words, Google will have a big advantage when they incrementally introduce a cost-per-acquisition model.
I wonder if Google is really a unique company and can innovate around click fraud, choosing the right time and place, and explaining a new system to its customers? I don't think the hard part is technical, I think the hard part is changing a the current system that produces a billion dollars a quarter. Who can make that bet, and can they do it early enough?