Location search by address not working

For some reason I can't search by address, only points of interest using my Garmin Edge Explore 2.

When trying to search by address (rather than store name or "bike shop" etc...) I don't get any results. I only get results if the address I search for is already marked as a point of interest.

I googled around, tried enabling and disabling the maps (Activity Profiles -> Navigation -> Map -> Map Information), right now they are all enabled (INTL Standard Basemap, Garmin Cycle Map EU, Garmin DEM Map EU, Garmin Geocode Map EU), but still, can't search for a specific address.

How come such a basic functionality doesn't work?