Locations Map: Show all location based on search OR go by the search area?

We are trying to create a locations search for the business so customers can locate it in maps on the company site. How it works is:

  1. The user types the name of the city in search they want to see locations for
  2. It zooms in to that city and lists all the available locations within the viewable area

As cities/suburbs come in all shapes and sizes we can't zoom out to the boundary so there is a predefined zoom level we have to agree to.

As you can see in the diagram there will be some locations left out of view. My argument with them is if the user types London for example in the result list we should list those that are outside the viewable area, even though we aren't zooming out to fit all locations within view. But they dismiss this and say this is a locations "MAP" search so the user has to move the map around to get it to appear in the results list.

My considerations are:

  1. Search is respected, the location IS in London we must list it
  2. If the user is searching on a slow 3G phone, they don't have time to zoom out to increase the viewable area, just let them select the location on the list to reveal Phone Number or Operating Hours.

enter image description here