Ballmer ruined the company, not turned it around. He took something amazing and tanked it. Nadella is the example here.
> Under Ballmer's tenure as CEO, Microsoft's annual revenue surged from $25 billion to $70 billion, while its net income increased 215 percent to $23 billion, and its gross profit of 75 cents on every dollar in sales is double that of Google or IBM.
...
> Ballmer also built half-a-dozen new businesses such as the data centers division and the Xbox entertainment and devices division ($8.9 billion) (which has prevented the Sony PlayStation and other gaming consoles from undermining Windows), and oversaw the acquisition of Skype. Ballmer also constructed the company's $20 billion Enterprise Business, consisting of new products and services such as Exchange, Windows Server, SQL Server, SharePoint, System Center, and Dynamics CRM, each of which initially faced an uphill battle for acceptance but have emerged as leading or dominant in each category.
It doesn't exactly sound like tanking.
MSFT Market cap when Ballmer announced he was leaving: $270B
That was the problem... even if the initial valuation was ridiculously inflated by the early tech bubble, post-crash, the stock was pretty stagnant throughout his tenure as CEO.
http://fortune.com/2013/08/23/steve-ballmers-market-cap-prob...
Ballmer gets credited with XBox etc, but I always thought MS was doing a lot of spray-and-pray management during the Ballmer years, and there were far more failures than successes. There certainly didn't seem to be any realistic strategy or vision. (I remember going to a trade fair with a huuuge MS stand showing off some kind of library or book management service. That product was dead less than a month later.)
Nadella seems to like strategy so much he has a handful running all at the same time. Which is how you get something like "Cloud-first, mobile-first" - which doesn't even make sense.
Point being that CEOs are there to signify the existence of leadership[tm], not necessarily to provide it - and markets and investors don't appear to be able to tell the difference.