As with all things, it's a matter of demand and offer. If a potential CEO has a choice between a company that pays well no matter what, and a gamble which could leave him out of a job and without money, he'll choose the sure outcome. On the other hand, a good CEO is such an important thing that companies will bend over backwards to meet their demands. So they do that. A few million bucks is cheap change for potentially higher earnings.

You might argue that incentivizing CEOs should be more important than getting a good one, but you'll have to ask shareholders at major companies why they don't insist on that instead.

Whether this is "deserved" or not is irrelevant. What matters is profitability, not fairness.