The approach I would take is this:
- Maps would be designed with specific ad locations, such as billboards and banners (this probably wouldn't be applicable until after a new map format is created, but it might be possible to do with the current one).
- Ad images would be located on a central ad server and downloaded in-game (just like a website, basically). Once downloaded, they'd stay cached so you wouldn't have to re-download the same ones (unless you reinstall the game).
- Advertisers could spend as much or as little as they wanted. The more they spend, the more likely their ad is to be displayed. If Company A spent $50 and Company B spent $150, Company B's ads would show up 3x's as much as A's.