Until recently, Google Maps only pointed to items from custom maps and geo-feeds, but now you can find the maps in the list of results. For example, a search for [president birth places] returns a map that shows where each president of the US was born.
You can restrict your search to custom maps and GeoRSS feeds by clicking on "show search options" and selecting "related maps". The index includes the public maps created from the "My Maps" interface.
Google Maps tries to go beyond basic queries like "pizza in ny" by using the web index. Google LatLong gives some examples of complicated queries that return useful results: bridge collapse in MN, falafel carts in nyc. Unfortunately, Google Maps has a very basic understanding of queries and can't always differentiate a general query like "places to go in London" from a search that asks for directions.