This can happen when the TLD on your menu item is not set correctly. The TLD must be set in the back end for geocoding then also on the Menu Item Component Configuration as shown here:
Searches are geocoded on demand, and the system needs to know what country the postal code is in.
Also, if you incorrectly set your TLD, and perform multiple searches, those possibly incorrect search results are cached so all future searches for that postal code will continue to return incorrect results. To clear that cache, click the "Delete Geocode Cache" just above the list of geocoding results on the Geocode screen in the back end.