Actually, i had such a problem. You problem is
the adress normalization. We solved it by using an external resource:
google maps - they are really good at that.
When someone enters an address, you do a call to google maps to
retrieve the coodinates of an address and save the together with the
adress.
When someone enters a search string, you call google again to retrieve
the
coordinates and then you search you database for addresses with
coordinates
that are within a certain radius.
If you know what your doing and you use a good geocoding-lib, thats
about 20-30 lines of code for both operations.
Regards,
Florian G.