That wouldn't work for dynamically injected ads that could be at different timestamps and have different lengths for each user.

Some sort of checksumming to detect segments differing between users would probably be doable.

I think you under estimated the cost of your solution, the cost must not excess the profit from the ad.

You need hard work on the encoder to do that (at least to segment video, because re-encoding dynamically is obviously not an option). Not profitable for Google.

Aren't there codecs that don't carry state across keyframes? Wouldn't it then be trivial to split a video at a keyframe and insert new content?

Sounds like it would be just as trivial to detect the split at the decoder level.

Why? How would you determine if the content that comes after the split is an ad? What if YouTube has 1000s of versions of the same ad, of which they insert one after the split?

Shazam-style audio fingerprinting can help.