They had been selling infrastructure (Windows Servers). They already knew how to sell infrastructure. In fact, most of the first sales of Azure were just as an add on to their existing enterprise contracts.
All of those were "cloud-adjacent" even in their proto-forms as on-premises–only offerings. Even if they weren't "real cloud infrastructure" they were big Capital-E Enterprise products and a lot of selling cloud is still B2B Capital-E Enterprise work at the end of the day.
Sure, but the point remains that this was a sales engine that was very similar. It certainly was a faster path for Microsoft to bootstrap cloud sales teams than whatever Google's long, winding path from ad sales to whatever it is they think they are doing with GCP sales.
(Though it hasn't seemed to work effectively for IBM. That may just be IBM incompetence as old school commodity-priced Mainframe mentality should be exactly the same as cloud sales. There's probably an amusing alternate world where IBM Cloud is using something like 1950s presentations only slightly modified to sell "cloud" in 2020, just because they could.)
Doesn’t matter, it’s the relationships that count. People from Microsoft eat filet mignons with the top 50 IT execs at every major company. That’s why any turd of an MS product can immediately get tens of millions of paying users.