I thought we were talking about consumer advertising, not business-to-business advertising. Still, if you want to include trade advertising in the discussion, that's fine with me: It just goes to show that Google was able to drive word of mouth through the strategic expenditure of limited ad dollars while AOL, MSN, Yahoo, etc. were spending millions on traditional consumer media.
The MSN online service, the X-Box, Microsoft games and other CD-ROMs (with the exception of Flight Simulator), and any number of other Microsoft products and services have been also-rans. Expedia didn't keep Travelocity from taking a good share of the online travel market.
Microsoft couldn't even make MSN a success when it was an integral part of Windows 95 with an icon on the desktop.
Contrary to what a lot of people seem to think, Microsoft is not invincible. (If it were, my industrial-strength hosting service would be running IIS on Windows NT/2000/XP instead of Apache on BeOS!)