Cannot Add Number In Teams - Location Not Found

Ok - the workaround:

1. Create an emergency location. (Click the add a location button on "https://admin.teams.microsoft.com/ > Voice > Phone numbers > Add" or "https://admin.teams.microsoft.com/ > Locations > Emergency Locations")

2. Navigate to https://admin.teams.microsoft.com/ > Voice > Phone numbers > Add 
3. Type some part of the emergency address created (not any part of the title), such as the street name, in the location box when adding a phone number. It should allow you to select the emergency address from a dropdown (with the titles displayed - go figure). 

Using a part of the actual address from the emergency address (and not the title itself) was the workaround in my case.