Postal Codes can actually be a headache because in some places they can represent very tiny areas as opposed to the US where they often represent relatively large areas (except in a big city where they may represent a few blocks).
Look at Canada, their postal codes can actually represent very very tiny areas. Two stores on opposite sides of the street often have different Canadian postal codes. Also in a list of Canadian businesses, when merging the list it is not uncommon to see the same address with a slightly different postal code. This just indicates that a lot of people get it wrong. On a customer basis I don't know how realistic it is that they actually get their exact zip code right.
http://www.columbia.edu/kermit/postal-ca.html
Basically it seems that each apartment or business dwelling may get their own zip code, which would make sense based upon what I have seen with Canadian business addresses.
The other point is that this is just Canada. Each European country will have its own address/postal code, so will Australia, Russia, etc... If you really want to do address verification, this is a major project.
To actually verify the address you need to to verify the postal code, city, and street. In the US the census releases the TIGER database files which often have a list of streets. But for other countries I don't know how you can get a list of streets. It may be best to look into a commercial package (maybe one of the GIS packages, although a lot of them only offer detailed addresses for the US/Canada and sometimes a few European countries).