The issue is more difficult with ad networks, since they always point to specific domains and run specific bits of javascript. But it seems to me that ad networks could simply offer a PHP et al script that publishers could locally host and include in their content that would basically proxy the connection between the user and the ad network. Clickthrough URL's would appear to be on the originating site, like any other content on the site, and the script would forward them to the appropriate site.
I have given this all of ten minutes of thought, and I'm on my way to a solution. I don't buy that companies with real money on the line can't solve this issue.