For services hosted in other countries the law in those countries might well have something it can say/do, but even if they do successfully put their feet down MS could just pull the services out (costing the country if the investment in equipment/services/employees is significant) and move them elsewhere. They might be able to add the protection needed under those non-US laws the nodes in the affected areas, it depends on the exact wording and enforcement of the law, but even if they did you lose that protection as soon as you hit a node elsewhere anyway.
Practically speaking if this is a concern for you (and it might legitimately be: contrary to what governments seem to think people and companies that are not criminal, not just the criminals/terrorists, have good reasons to want some privacy generally and more specifically those in competition with MS (amongst others) would not want to trust them as the gate-keepers) then your only option is to find an alternative to Skype. That isn't going to be easy though: any commercial provider is going to comply with the same regulations otherwise they'll find it difficult to operate in the US market (or the Chinese market which is growing much faster and is even more spy-y than the US) and even if you find something you then need to convince other to use it too.
The actual hosting country does not always matter. In the Netherlands for instance (i can't speak for other countries) -where- a service is hosted is irrelevant. If you market your service to Dutch citizens (you have a Dutch language version of the site, or a Dutch contact number for instance) you are assumed to abide by Dutch law and can be prosecuted in a Dutch court if you don't.