My question is: how does one do this?!? It seems like the only way we can purchase international domains is if we have a local address / legal rep in the countries where we need to acquire the domain names for. That's what we're being told by domain name brokers.
Any idea how to work around this?
For those that aren't restricted, there is no issue.
For those that are restricted, it would depend on the actual restrictions as to what will happen. You will find that the majority of ccTLDs will be 'semi-restricted' and that they will require a local admin or registrant contact. You should find a registrar, I would suggest corporate and not retail, who will be able to assist you. In many cases corporate domain companies will have built up relationships with local registrars and trademark agencies so that they are able to offer their clients proxy registrations. There are additional fees involved for providing proxy registrations, so get several quotes before deciding who to go for.
For those countries with trademark or definite local presence matching company name requirements, the question is how important these are to you. If you are trading there you can probably register via your local office. If you're not trading there you must consider if anyone else is likely to register there due to them facing the same restrictions.
Amos