imho, the biggest reason for his ouster was that he had no internet strategy - his plan A was buying Yahoo. No innovation, no imagination, no results.
Azure is a decent extension to the MS development ecosystem. Xbox and Xbox Live seem to be doing well -- I don't use either. Bing, while not Google, has it's fans.
Where MSFT was late to the game is in their approach to the post-PC era. WinCE/WinMo were "ok" at the time, then the iPhone came along. Win8, Surface, WP8 are all relatively new - do I expect the same success as, say, XP or the like? Not really, but that path is still playing out for them.
Couldn't we have said the same thing when Apple lost to the IBM PC when they didn't "get" business computing? (the debacle that was the Apple III - a supposed "business" machine)
It started with focus.
It has been awhile but at one point MSFT spent more on pure research than AAPL did on their whole R&D budget. Research takes time, but AT&T and IBM aren't doing much of it these years. Investing in research is another plus, not in the near term.
Windows Phone/Mobile, Surface, Xbox, Search Engine, and Azure are all effectively this model. Hackers place a high value on innovation, but continuously increasing revenues with this 'embrace and extend' + kaizen model seems to work for them so far.
Apple are exactly the same too. The stuff I love the most has come from elsewhere.