To the extent that a company does have subsidiaries and they are located in other countries, then yes, those should be treated as different companies because they are structured in that manner. This is fairly common for tax reasons, structural subordination, valuation, liability (legal) reasons, etc.
To the extent that it is one company with no subsidiaries or other related entities, operating in more than one country, then it comes down to the laws of each respective country. In international law, there is really no set in stone law but rather a bunch of vague treaties and understandings that countries are really not necessarily obligated to follow. There is no international army or police force so there isn't really any teeth to enforce much. Therefore, two countries could in theory say one company is a native of each of them - and the company could say they are native of a third country altogether. What matters more for these countries is the appearance of uniformity and the appearance that they are on the up and up and that they are reasonable and make sense. They also want to attract other companies to do business there and receive their tax revenues etc. This also means that the company must agree to pay those tax revenues. So what occurs is an gradual reversion to an acceptable mean, which we all view as the international law or standard and over time this has become more and more uniform for and amongst countries in the aggregate taking into account what businesses ultimately want too taking into account taxes etc.
The way it works from a liability standpoint etc. is that a parent company owns stock or shares or interest in the subordinate company so if the subordinate company makes money and this money is distributed to the parent there will be taxes accordingly. Also, if the subordinate owes something and can't pay the parent will lose its ownership if they do not transfer in money (bankruptcy means the creditors win not the stock/share/interest holders).
So, in short, they are recognized and treated as separate legal entities because they are only if they are. A single company can still do operations in multiple locations, but the advantages of structuring separate entities may be more important and more profitable (tax reasons etc.) Whether others will recognize entity relationships depends on the names for each etc. (or research conducted to find owners). A lot depends on the structure that the company sets up for itself which is governed by a host of issues as mentioned above.