What Microsoft sells is a "good enough" solution that speaks the right language for the decision makers. In turn, this makes their decision less risky while still satisficing the requirements.
If you have an existing business relationship with a company and already trust them to help you navigate regulatory hoops, there's going to be strong inclination to continue to trust them as you expand your infrastructure to the cloud.
Like you said, it's the kind of very smart, long-term marketing I tend to associate with "New"/Nadella Microsoft.
I still don't trust them, but credit where credit is due.
Namely, if you were to state to a higher level manager that you "don't trust Microsoft", you will come across as a crank. Or a developer who doesn't see the bigger picture.
To improve perception, folks should try to reframe their personal preferences ("I don't trust MS") as risks to the business - "I worry that MS will lock us in to their platform and jack up prices". The former is reputation-harming; the latter is being a savvy 2nd order thinker, who looks beyond just what the MS salesman says.
The next one would be the PRISM connection (Skype architecture, etc), and FISA orders they're surely under.
It's not totally they're fault I don't trust them. Buuuuut, it is partly.
Definitely appreciate the feedback - lucky for me, I have removed myself from corporate tech bureaucracy, become self-employed, and can preach from my poor man's pulpit ;D