Can any internet company be publicly ordered to break laws in other countries, regardless of where it is based?
Why shouldn't they? MS is a United States company. Why should MS, or any other corporation, be able to only abide by US law when it is convenient for them, and break it other times? If the laws of two jurisdictions are incompatible with each other, the corporation should have to make a hard choice and only operate in a single jurisdiction, and use other avenues to expand business to the other.
This is not a case of the US trying to compel a European Company into doing something, it is compelling Microsoft, subject to US law, to turn over data it holds, albeit in a different company. If an American individual is subpoenaed for information relating to a crime, resisting turning it over because it's held in a safe deposit box abroad, is no more an acceptable excuse than "it's in my other pants".
An individual in the United States must abide by US law even when abroad, in addition to abiding by the rules of the foreign country. It's still illegal for an American to smoke weed or solicit 14 year old prostitutes abroad, despite those being legal in some places of the world. If American persons have to play by United States rules 24x7, why should a corporation get to pick and choose?
The US legal system starts and ENDS at the US borders. You seem to have completely misunderstood this situation, For example your safe deposit box example, if the US wanted the contents of a safe deposit box in Europe they cannot legally seize it, doing so would be a violation of europan law and the US officials doing it would be guilty of bank robbery and treated like any other common criminal. They must go through the countries legal system that holds the goods they want to seize, similarly the same applies to Data, the US can get access to it as long as it follows the appropriate laws and procedures. What the US government is trying to do is say other countries laws don't matter with data and therefore are asking a US companies to break another countries laws. You yourself said it that when in other countries you must abide by that countries rules, you cannot compel an individual or company to break the laws of another country. No one is suggesting that MS gets to ignore US laws, it is the US government saying that they get it ignore other countries laws and can compel US companies to do the same while they are in those countries.