We knew this day would come (and have been talking about it at the past several conferences). Yahoo! has been doing a version of this for some time with its sponsor "icons."
Consumers will want some version of this and so it doesn't risk destroying the user experience if it's handled thoughtfully. Indeed, we would expect to see more of this as maps become more and more central to the local search experience.