I am wanting to create a set of database tables that will not be overly complex that will semi-normalize address information. Right now we only have to be concerned with US addresses, but I want to design for the possibility of expanding into international addresses.
I know that there are address verification web services out there, but we do not want to go that route (too pricey), but I am having a difficult time finding any standardized international address formats to base my table structures on.
I'd suggest checking the International Postal Union web site. They have enough discussion of the issues to give you a good idea of how to cope with the addresses you might encounter.
Just FYI, pick a sub-set that will cover most of the addresses that you'll need at first... Trying to create a "universal address" database is a huge task, that rarely pays off very well. Very few businesses truly need to be able to address mail to everyone on the planet, and they usually already have the address expertise needed.