While "getting a database" is a good idea, it may not solve this person's problem. The problem is, given a large volume of legacy, unparsed, free-form address data, how do you parse it to put it into the database in the first place?
Unfortunately, that's difficult. Lingua::EN::AddressParse is good if you know what country the address information is for, but it isn't sufficient by itself if you also need to extract country codes from international address data.
I'm actually about to solve a similar problem myself. If I can't find consistently exploitable patterns in the data, my next tactic will be using Lingua::EN::AddressParse in combination with state/zipcode verification to try to catch all the US addresses, and then to try to exploit patterns in the remaining (international) addresses that AddressParse can't parse effectively.