I don't think anyone would argue that Ballmer's been the most innovative CEO of his era, but as a custodian of shareholder value, it's pretty hard to fault him. Could he have done better? In hindsight, we know the answer is yes, but the answer in hindsight is always yes. He managed to try and fail at big ideas without bankrupting -- or even significantly impairing -- his company. Not many CEOs can claim the same.
What happened to Microsoft? It built and sold unsexy products that people were willing to pay gobs of money for. I'm sure many businesses would love to fail so successfully.
 http://www.gurufocus.com/financials/MSFT#cs. For the sake of reference, AAPL returned ~$26 billion to shareholders over the same period.