Proximity search doesn't always work for towns
I've had something like this come up and so when I looked at what CiviCRM was doing I noticed it doesn't use all the available fields. For example it uses City but not County. It also only uses the first line of the street address, so depending on what you have there it may actually return nothing even though city, postal code, etc without the street address would work.

You can see what fields it's combining here:
https://github.com/civicrm/civicrm-core/blob/master/CRM/Utils/Geocode/Google.php

You can also put the contact's address into maps.google.com directly and see what it returns, to help troubleshoot.