A map that draws correctly and a search that finds nothing is a specific combination, and it points at one thing: the map is served by the Maps JavaScript API, but the search box needs Places and Geocoding as well. If only the first is enabled, you get exactly this.
1. Check all three APIs are on
In the Google Cloud Console, under APIs & Services, confirm that Maps JavaScript API, Places API and Geocoding API are all enabled on the project your key belongs to. "Map is not working correctly with my Google API Key" walks through this and the other key checks in order.
2. Check which Places API you have
Google now ships two generations of the service. If the one on your project is listed as the old Places API, that is worth changing: enable the current one. If you cannot tell which you have, the safe move is to enable the current version alongside it and let the newer service answer.
3. Check the referrer restriction
A restriction that allows your shop domain but not ours lets the map load from cache while the search calls are refused. The address that has to be allowed is:
https://sl-widget.proguscommerce.com/main4. If you are not on Google at all
Only the Google provider uses Google for search. On the other providers, address search does not go through a Google key and none of the above applies, so tell us in the chat what you are seeing instead.
Stuck on any of this? Open the chat in the bottom right corner of the app and we will help you set it up.