(1) Microsoft is a US Corporation
(2) With the Skype acquisition, Microsoft (arguably) becomes a telecommunications carrier.
(3) CALEA passed in 1994, "requiring telecommunications carriers and manufacturers of telecommunications equipment modify and design their equipment, facilities, and services to ensure they have built-in surveillance capabilities, allowing federal agencies to monitor all telephone, broadband internet, and VoIP traffic in real-time." [a]
My (unfounded, optimistic) speculation is the skype acquisition was strategic positioning in the mobile market: seamless cutover to skype when your phone has WiFi.
a - http://en.wikipedia.org/wiki/Communications_Assistance_for_L...
Whether it's for or against our interest was never addressed.
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.
But they were still legally required to have done so, and the DOJ could have sent them up shit creek if doing so ever became a priority.
What's changed now? Probably just that Microsoft's legal division wasn't comfortable having that kind of regulatory non-compliance under their watch. Microsoft gets a lot of scrutiny from the DOJ and probably aren't particularly keen on being hauled up on new charges over this issue.