2: The primary method of cheating in print was lying about your circulation numbers. Anyone could easily verify that the ad was run in the agreed on spot, but the question of how many people read your paper/magazine is harder. In the US circulation numbers typically come from the nonprofit Alliance for Audited Media (formerly the Audit Bureau of Circulation). See https://en.wikipedia.org/wiki/Newspaper_circulation
3: The world is moving in that direction, but not especially because advertisers or publishers are pushing for it. Instead it's consumer advocacy groups and browsers. My primary project at work right now is (along with a lot of other people) figuring out how we can serve personalized ads without cross-site tracking (https://github.com/WICG/turtledove).
4: An ad network is a middleman between advertisers and publishers. Directly connecting pairs of publishers (P) and advertisers (A) scales at O(PA) while publishers and advertisers both connecting to a network scales at O(P+A). AdSense would be an example: an advertiser who signs up with AdSense can advertise across all its publishers without needing to make 1:1 deals.
(Still speaking only for myself)