Ads in desktop software have seemed on their way for a long time, but the only high-profile bundled-with-the-OS example I can think of before this is Apple's Sherlock that came with Mac OS 8.5 and 9.

That was a bit of a special case, for similar reasons to the ones in Metro apps. Search engines had ads anyway, so ads in a program that gave you search results in a desktop app wasn't a huge leap. (There was still significant backlash, though.) And ads in mobile apps are fairly commonplace, MS has just gone a step further integrating them into their first-party ones. Which is a curious decision—how much revenue are we really talking about?

I also feel like there's an interesting parallel between Sherlock—a specialized program for getting results from the internet—and "apps" in the mobile sense. They're both ways to get around at-the-time-limited web user experiences. Desktop apps like Sherlock, though, did not last particularly long as the web itself got more usable.