Bill Gates had vision. He wanted to change the fucking world, and he did. He put a PC in every house. He also had vision for how to run a business, and he (rightly) gets a lot of flak for that vision (i.e. forced integration), but it was effective in making and securing Microsoft's dominance.
Ballmer has not demonstrated vision in anywhere the same level. He seems more like a manager than the leader that Bill was. He has continued to execute the same vision that Bill had, or sometimes just goes through the motions. Bring products into new emerging markets (cloud, mobile, etc) and a huge reliance on enforced integration (lock-in). Throughout this, the original strategy that drove these methods has remained unquestioned, and often forgotten altogether.
Microsoft needs to question its original strategies and decide if they're still working, and either what is needed to make them work or what can replace them. For example: Forced integration. The idea is that if someone wants part of the MS Stack, you upsell them the rest of the MS Stack to get the full potential of the part they want. The problem is that if someone wants part of the stack but not the whole thing, will they go all-MS, or will they forgo that one part that they might have gotten in isolation? Back in the day, MS was dominate enough in some spaces that they could force their way into other spaces with integration. Is this still the case? I suspect it is far less so. Other companies and FOSS has made an entirely-non-MS stack viable for a variety of uses. Playing nicely with, say, Unix may be a more worthwhile strategy than it used to.
Similarly, Microsoft used to get into a whole bunch of emerging markets in order to dominate them, not for that market as such, but in order to prevent competitors from emerging. Does this still work? Not as much as they would like. Google and Apple are pretty well established in mobile, and Google is pretty well established in search (on the other hand, the XBox won). Take a look at whether chasing your competitor's products is still worthwhile, from a strategic view (the answer is likely to be neither yes or no, but a question of picking your fights better).
Now, I don't know enough about the various markets to be able to say for sure that MS should embrace Unix or ditch WinMo 7 or whatever (I like Bing, personally, and hope it succeeds). But I do have the strong suspicion that that question has not been seriously asked in the first place. As an outside, Microsoft's strategy & vision looks like it has become cargo-cult-ish in the last decade or two, following in the footsteps of Bill because he knew what he was doing. That could even have been a good idea a decade ago. But the world has changed. Old practices need not be discarded, but they must at least be examined. If you create a new vision for Microsoft in the 21st, and stick to it, many of the other decisions are much easier.
EDIT: The other thing I would add is that products need to better focus on the question of "Why would I use this?" Xbox succeeded because it answered that: Xbox Live. Zune, despite being (according to some critics) better than the ipod, did not succeed because it either didn't have or didn't communicate any compelling reason why I should get a Zune. Bing is facing the same problem. Office 2007 was really cool because rather than focusing on what it could do from a features perspective, it focused on what the user needed to get done and resulted in a more productivity-focused tool. I am pessimistic for WinMo 7 because I haven't heard why I should prefer it over other smartphones.