I'd recommend an addressing tool like Quick Address (www.qas.com) which we use in the UK, Belgium and the Netherlands.

Elements which appear in UK address data are:
Department name
Organisation name
PO Box
Sub-building number
Sub-building name
Building number
Building name
Dependent thoroughfare
Thoroughfare
Double dependent locality
Dependent locality
Postally non required locality (PNRL)
Post town
County
Postcode
Postally non required county
Delivery point suffix

Though to address a letter you wouldn't use all of those!

We get by with 5x c(50) address lines, postcode c(20) and country c(3).
We use the 3 character ISO codes for countries. You could get by with the two character ISO codes.
The meaning of each line changes depending on the country and we have a class for handling addressing for each country.

If you're going into the rest of Europe after the UK bear in mind the European postcode format is different. Also the customary printed layout of addresses is likely to be different in every country.