Welcome to WebmasterWorld Guest from 22.214.171.124
Can anyone recommend a company or even know if there are companies that do this?
There are some ways around this problem for some countries, with a number of companies offering services whereby they offer the 'local presence' for an additional annual charge.
I've found Safenames and Speednames to be of use for global domains in the past - Safenames in particular has comprehensive details of the individual registration requirements for each country, which may be of use to you. There are other similar companies offering foreign registrations, including Verisign's 1stGlobalPlace.
If possible, it's easier to hold all your domains with one company - makes administrative tasks, changes to nameservers and the like much, much less painful!