This question is an invitation to explore the intersection of business and technical considerations in a particular business market (web service hosting).
The choice of offerings (OS being the primary determinant here) is fundamentally one maximizing ROI. How much does it cost for you to create an offering (capital outlay), and to provide and maintain it (unit and overhead)? How much can you charge for it? What's the market size (how many customers do you estimate are willing to pay your price)?
You only mention two offerings: MS Windows and Linux. That's almost the total market ... there are sliver thin niches offering FreeBSD, Solaris, MacOS X, etc.
As you point out most of the available vendors offer Linux and do so at a considerable discount over the available MS Windows offerings. Obviously Linux is free (no per unit capital expenditure for software licensing). Linux has become widely known among technical professionals (development and support staff are reasonably easy to find). Linux, in any competent configuration, can run with considerably less hardware overhead (further lowering capital overhead, since you have a higher capacity on comparable hardware).
Furthermore there's a huge market for Linux servers (VPS or co-located). Many popular applications (Apache and many modules, PHP, MySQL, and quite a few wiki, blog, and other offerings are readily available for it.
MS Windows is more expensive in every regard. Initial capital outlay is significantly higher since you have to create your own "dashboard" and "provisioning panel" applications ("cPanel" for Linux is commercial ... but widely understood and reasonably priced, for example; GNUpanel exists as an alternative, though I don't whether it's mature enough for most businesses). Unit costs entail licensing fees to Microsoft. Maintenance costs are higher (Linux admins tend to be marginally more expensive, but the most recent credible study I've seen suggests that reasonably competent Linux/UNIX admin can manage about four times as many servers as a comparably experienced MS Windows counterpart).
On top of that the size of the market seems to be much smaller. There are fewer customers (mostly because your offering price must be higher for the aforementioned reasons). Yes there are some ... there are developers and applications which are only supported under MS Windows based systems. There are some customers who are willing to pay a premium for MS Windows based hosting.
Mostly, however, the market is dominated by price. The number one factor for most of these hosting sites is which can offer the lowest price for an acceptable level of performance and reliability. (A few reasons why price is takes priority for so many customers: it's the one unambiguously quantifiable objective criteria they can readily find; too many vagaries affect power and 'net reliability and there isn't a widely recognized objective comparison of the other factors).
Certainly Microsoft has struggled to increase their penetration into this market. However, they have yet to find a way to gain more ground in this particular market. I've heard that they paid a number of domain hosting providers to use IIS on "parked" domains (in an effort to skew the Netcraft statistics). However, most of their efforts seem to have been focused on expanding their lock-in in the development tools chain (offering the IDEs that more developers want to use, thus locking them into .NET) and trying (in vain) to lure hardware vendors into new forms of lock-in (like the abortive "legacy-free" PC99 spec. they tried long ago, and variations on the "trusted computing platform" and so on).
Honestly I can't think of a combination that would really help them. They could offer a "free" (no-cost) starter edition just for hosting/co-lo providers of their platform and tools set ... and try to sell up from there. They could couple this with a client package (basically a buffed up Frontpage). They could offer a cPanel package to the providers for free (initial cost) and perhaps even some commission on any upsell garnered through that provider's offering. I don't know if those would be compelling enough to compete with free (libre).
(Personally it wouldn't work for me; but it might appeal to enough of a segment to be statistically significant).