This isn't seizing. This is ordering an entity to produce evidence. Yes, the US could order a US company to produce the contents of a safe deposit box in Europe. If the company doesn't comply, the US arm would be fined until it does comply. That is if the US couldn't get cooperation from local authorities to get it seized.
The US government isn't saying anything about other countries' laws not applying. The US government is saying its own do. Where there is a conflict, it really isn't the US government's problem, it's MS' problem.
And this whole thing works in reverse too. US companies in the EU are required to comply with EU laws, including producing evidence that is outside of the EU.
Just to wonder, if you really believe that out of the US is out of the US' reach, you must be really shocked to hear of the IRS now finding out about money in offshore accounts and taxing people on it, eh?