I live in one of those countries and I think people are over-analysing the problem. I think you're perfectly safe with:
Addr 1 (req) Addr 2 (optional) State (req but including "Outside US") Country (req) Post/Zip Code (optional outside US)
When I order stuff from the US I just put my city and state in the Addr 2 line.
In the end this is a classic example of the "perfect being the enemy of the good". Look at where your sales are going and allocate validation efforts accordingly. A lot of sites include Canadian provinces in the "state" field for example.
I'm still working on my address support. It's hard, considering there are more de facto countries than are legally recognized by any international body, and most of them are one-offs in terms of address formatting.