Google is testing placing icons within Google Maps, for some Google Local searches. For example (it only works if you are on a PC), conduct a search on booksellers nyc at Google Local. You will notice little coffee icons in within the maps. If you click on the coffee icon, you will see a "sponsored listing" for Barnes and Noble. This was first discovered by Shimon Sandler and then I blogged it over at the SEW Blog (check the SEW blog for screen shots of this in action).
In the past, Google tried sponsored listing in Google Local and Google Maps with blue balloons.
Forum discussion at Search Engine Watch Forums
