Maybe a good approach would be to use a format that somehow fits 99% of the addresses and a link on the bottom of the form with the text "Problems fitting your

Maybe a good approach would be to use a format that somehow fits 99% of the addresses and a link on the bottom of the form with the text "Problems fitting your address in that form?". When the user clicks the link, all the fields of the form would be substituted by just a multi-line input field. Then you have a solution for the 1%.