Most modern video formats can be sliced and spliced at certain frames without needing to recompress or anything like that. If you operate all your own cache servers (which youtube do, AFAIK) you could splice a different ad into every stream, in real time.
Youtube would have to be careful, as plenty of users are used to being able to refer to timestamps in the video. Right now people are used to telling someone the interesting bit is 2735 seconds into that video lecture, and that's a time without ads counted.
Even if you splice on a geo & language basis, there are two basic kinds of interest-based audience targeting: content and users.
Putting ads on topic-specific content is OK for brand advertising, but you got to watch out for saturation - you're wasting money if you show the same ads over and over again to the same person. So you want to stop showing a brand ad if someone has seen it too many times already.
Showing ads based on user interests has better performance for action campaigns. It relies on some way of tracking the user and / or their interests, but it leads to better conversion as part of a marketing / sales funnel. So you need to select the ad dynamically based on the interests of the user.
All this adds up to making it hard to avoid dynamically choosing the ads to show. I think it's still probably possible with careful I/O to do the media stream concatenation server-side, and I expect it's probably the direction things will eventually go, as long as latency etc. works out.