That's the most interesting thing here.

Microsoft clearly knew this would be unacceptable, and obviously would have known Google would have to tell them to remove the app.

So it's clear that the whole thing is an exercise from Microsoft, I suspect, to paint more of the "evil Google" picture that they are working assiduously to establish. Now they can point to Google and say "look, everyone, Google is taking away your toys, they must be evil!".

The problem they may have is that this is pretty transparently unacceptable on their part, and even worse, it doesn't jive at all with their general stance on intellectual property (Android infringing on their patents, etc.) where they paint themselves as the good guy who always licenses IP and expects others to do the same.