1. From a REST point of view - the map is the resource. The adddress is well, not really a resource (the logic goes like this: if the address is the resource, the browser as a resource getter should only get the address, not the surrounds). IMHO the address should be modelled as an element of the resource, accessible by Maps' javascript.
2. Of course you can have nice URLs without being indicative of RESTfulness. Consider an address in Japan. They do not have road names, instead, they use building/block numbers for naming/addressing. While that can still be modelled as a nice URL, the convention is now flipped, and people will be confused
3. Consider that some places do not actually have an address. Like my former residence. Due to changes in the roads, my place had a new road with no name, and no actual address (well, eventually it did, and the road still has no name. Getting pizza delivered was tough)
What can be done of course is a bit.ly kind of thing, which I think will work. Something like /maps/199-valencia-street-san-francisco-california-united-states. The current google maps url is already kinda like that (with ?q I believe)