U.K. sites that require addresses often ask the user to provide a postcode. The site then offers the user a choice between the different addresses that match that postcode.
How can I match a postcode to a street address?
I believe you need the Royal Mail Postcode Address File. From that link:
PAF is the only complete source of all known UK Postcodes.
Services do exist to handle requests for this info, such that it may be cheaper to use such services for small numbers of requests (obviously you have issues as and when such services aren't available for whatever reasons).