I work in the address verification field for SmartyStreets. Actually we added geocoding and residential/business indication (RDI) features to our address API not too long ago and so I think I can point you in the right direction as you do your own research to find what fits your needs the best.
You'd be interested to know that Google and Bing may know more precisely where the store is, but their API has various limitations because of price, TOS, and functionality. For example, you can't perform automated queries against their service because it violates the TOS. And when you give it an address, it doesn't actually make sure the address exists: it does a best guess which is OK for some things, but when you want to pinpoint a business, you will want to ensure the address actually exists.
This is where a service like LiveAddress would be handy. While it doesn't supply the map, it does verify an address to ensure its validity. It also returns approximate coordinates. To render it on a map is pretty simple: plug the verified address and/or coordinates into a Google Map and, as far as I know, their Static Maps API can return a static image of a map location.
I haven't looked into too much detail there, but since you already know the address and coordinates, simply rendering the map with a marker won't violate any agreements, and will reduce your query count considerably. If you have any other questions about addresses, I'll be happy to personally help you with them or explain a bit further.