$22 Billion to $77 Billion in annual revenue between when he became CEO to when he stopped in 2013. I think that's pretty decent. I think that it was growth in enterprise that they were successful with.
Microsoft's share price didn't go up much because they paid out large dividends. If you look at total return people who owned shares in Microsoft did very well.
(If you look at a company's share price, you will see a drop roughly equivalent to the dividend per share each time dividends are paid.)