to many addresses

We have about 20,000 addresses in our database.

If my users are filling out a form that requires an address already in our
database I have to make sure they enter it in a format already in the db
(such as "West Road" not "West Rd.").  I have to also allow for new
addresses.

Obviously having a dropdown of 20,000 entries and a second field called
"Other Address Not Here" will not work.

It would also be nice if the field auto fills with suggested addresses from
the database.

Does anyone have advice on how I should do this?

I have been scratching my head over this problem all morning.

-Matthew