It's not hard necessarily, but you do need to get it right for each individual country. I can understand a company exec just not wanting the hassle.
You can employ through contracting agencies in the target country that handle all this stuff, but you'll still have a certain amount of pain when you run into different countries' Ideas of what is appropriate behaviour when firing someone.