They would need to resolve all of the domains, and compile a list of IPs.. but one problem that jumps out to me is geodns/round robin policies/etc. If LE makes a dns request, they can't be guaranteed that they're seeing all of the IPs for a domain.
For example.. if a number of domains are at a CDN (that does not use anycast)... they may all resolve to a single IP (to LE, from the location they're requesting from)... but really that CDN may have hundreds of IPs that are all valid for those domains. LE would then add that single IP to the list as a shared IP, but LE verification requests sent to those other IPs would still be vulnerable.
Even then, you have a CA sticking out its neck on the assurances of a web host that isn't accountable to the root programs and isn't accountable to the CAB Forum.
If that web host swears they don't have the issue, LE tests them, whitelists them, and then subsequently... at a customer request or just to be nasty the web hosts reverts and allows this exploit, the web host won't be held accountable. The CA will.
Ok, in this scenario, we have a web host with an adversarial entity on its server, that commits a crime.
By the same token, if that web host were hacked and used to obtain a nefarious certificate, would the CA be accountable? It seems to me that, as a customer, if you point your domain (which you must do somehow) at a hosting provider, then any DV issued with that hosting providers' infrastructure should be considered to be the responsibility of the hosting provider and domain owner. I think you and rgbrenner are making perfectly valid points for high-value infrastructure, which has in my view very little to do with these hosting providers. The fact that people can upload certificates at all for domains which they have not proved (to the hosting provider) ownership of is disturbing in and of itself, even if it is quite common.
For example.. if a number of domains are at a CDN (that does not use anycast)... they may all resolve to a single IP (to LE, from the location they're requesting from)... but really that CDN may have hundreds of IPs that are all valid for those domains. LE would then add that single IP to the list as a shared IP, but LE verification requests sent to those other IPs would still be vulnerable.