The accuracy of the geocoding can vary depending on the availability or quality of the address provided. The map must be configured to appear only with minimum geocode accuracy. This is set in the configuration section in the "Detail Display" panel. You can see how accurately a contact was geocoded on the "Geocode" panel when you are editings a contact.