So, what's the proper way to deal with this then?

Ask a series of questions and adapt the follow up to the questions depending on the answer given.

Starting out with 'select your country' and then expand from there, the more you know the more you can narrow down the remainder of the input.

That would be a nice little widget to be able to throw onto a form 'world accurate address input fields'.

And for some localities it will indeed display a freeform text field, but for localities where there is more structure it could supply that structure and make certain bits mandatory.