If they're underpaid, there should be a positive correlation between CEO pay and corporate performance (i.e. the companies that pay the most can hire the best people). If they're overpaid, there should be an inverse correlation (i.e. the companies that pay the most are likely to overpay the most, and thus waste the most money). So the exact middle ground implies--the exact middle ground. I didn't realize the market was so efficient.
The other possibility is that CEO pay or market performance are totally random. But all you need to do is identify a few very effective and very well-paid CEOs to argue that this is false. Just look at e.g. JCP's new CEO (they nabbed him from Apple thanks to, in part, a generous options package).
This might be clearer in another context: it wouldn't surprise me to find out that your average hunger in a given day has no correlation to your daily caloric intake. That wouldn't imply that calories don't satiate hunger; it would imply that most of us eat something close to our daily calorie requirement.