The only problem with the canadian postal codes and using the first byter to determine the province is that both the Northwest Territories and Nunavut both use X as their identifier.
I will have to do this on a country by country basis that way I can introduce custom code per country. I have a book that contains the address formats of 193 countries, and I am using that as a starting place... I know this is massive, but there is nothing out there that does anything like this, and anyone who does any type of database work with international data will have a need for this.
I have had a need for something like what you are doing. I gave up and just used 4 lines of free format text, except in the case of US addresses, for which I had formatting rules. What book has the address formats of 193 countries? I might buy that one.