I would reccomend just a single input for name, not all names are logically separated into just two parts, some people have just one name (such as Teller, and if used for addresses, the name may be a company name). Labeling is complicated since first and last name is not the same as given and family name, if names in your language is normally in which field should the first/family name go and the last/given name go?
For an address input you need:
Name/Company: <text box; no validation or munging>
Address: <Multiline textbox; no validation or munging>
Country: <text box or select-box if you're paranoid>
Making it more detailed and you're creating problems for foreigners.
The only thing your local post service need for a foreign address is the name of the country. The rest is country specific and may include several fields or in some cases something like "behind the church in the woods" etc.
Do not include zip code or anything country specific like that unless the user has chosen a country you have extensive knowledge about. People tend to know how to type their address in a free form text area, but they may actually mess it up if they have to force their address into foreign fields.
The worst you can do is silently discarding invalid fields. That happened to me when registering my address (in Norway) for a magazine subscription from USA. The norwegian addres format is:
<Name or company>
<Street name> <house number>
<post code> <city or suburb>
NORWAY
But when trying to force these fields into the closest equivalent in a very US-centric form they ended up mailing it to:
<my name> Oslo/OSLO//<And a lot of garbage letters and symbols>
/NORWAY
It eventually arrived, but it was a month delayed. It probably helped that I have a unique name, and that we're only about 5 million people in Norway. I doubt it would have arrived if I my name was "John Smith" and lived in New York and some web form had munged it to John Smith NY/New York;/ USA///
Sorry for the long rant ;)