try GPStoday,
http://www.geoterrestrial.com/
its not as featured as google maps or live search, but it will let you save whatever address you are at as a contact, and it takes all your contacts and puts them on the map.
it runs on your today screen, i think it has some good info on their. they're not quite at a 1.0 release yet, but its free and works fine.
good luck