So maybe there could be 3rd party company to check such things. Also ads could be sold at auction. I.e. auction for 24h display of ad in header from $1 on some news site.
Actually that's not a bad idea. Why not hit the site that the ad's are reportedly on from some IP addresses unknown to the ad provider. Do this over and over again until you have enough data to assume that say 1/5th of impressions are you then compare that to a neutral 3rd party source (Google Analytics comes to mind) of the total hits for that day. 5000 hits / 1/5 of those are impressions of your ad = 1000 impressions. Compare this to the numbers provided by the ad provider itself. All you'd need to do is spot check and it should keep everyone honest. I'm surprised people don't do this already.