You are right weed, just the thing to expose the problem in all it's complexity. Makes the push for post offices around the world to publish and enforce XML address schemas a screaming neccessity.
At least here in the UK we have standard Post Code that everyone can use. You can even get a database of them. With the post code and a house number you can look up every address in the UK, no need to worry about validating the rest of it. With the post code alone you'll get 1-10 addresses, all in the same street.
Hell, with the post code you can even look up the latitude and longditude of the house, or a street map, on the Ordinance Survey's website.
Which still begs the question, what kind of site are you passing the info to, Glyndower? Just a pity they don't have post codes where you are Glyndower.