No. If there's no correlation between CEO-pay and performance/market cap, finding a few interesting counter-cases doesn't further your argument. Inherent randomness and lack of accounting for other factors are far more likely to be the culprits here than market efficiency.
EDIT: Further, zero correlation isn't a "middle-ground" between positive and negative correlation. If it implies anything it's that one variable (performance/market cap) doesn't depend on another. If there's no correlation, CEOs can still be overpaid, they just can't do worse for their companies as pay increases.
1. There's an efficient market, and CEO pay reflects the extra value they create. In other words, a $100 million CEO is worth $50 million more than a $50 million CEO, so your economic outcome is the same regardless of which one you hire--except that larger companies will extract more value out of a given level of managerial talent, since they can amortize it over more underlings/revenue/whatever.
or
2. CEO pay and company performance are totally random. But for that to be the case, you'd have to deny that there's any such thing as being able to identify and pay for a talented CEO. Maybe! But every time I've interacted with large company CEOs, I've noticed that they tend to be very bright, and they work extremely hard. People who are in the 10th percentile of public company CEOs--the kinds of people who bankrupt companies--still seem to be in about the 90th percentile of smarts and energy.
I don't know of another theory that could explain the data as presented. Either the process is random, or it selects for people with certain valuable skills. If the system tends to promote skilled people, you'd expect the companies they run to have a higher return. Unless, of course, they capture that value for themselves.
You can be extremely bright and work extremely hard and yet fail to produce a desired outcome due to forces beyond your control or understanding. It's human nature to overestimate our degree of control over events, and indeed, CEOs are probably selected for this trait more than other professions. Who wants a CEO who admits he really doesn't have much influence over the fate of a $100B enterprise? No, you want someone who is self-confident to the point of delusion.
But in actuality, all else is never equal. Then we use the outcome of that unequal scenario to judge after the fact who was the smarter and harder-working. In poker you have a very regular, controlled game. Imagine a tournament where some players were randomly given extra aces, then try and figure out who the best players really are. That's the corporate CEO market.
What you're suggesting here is not that there's no correlation, but that there is a latent correlation hidden by the market. Another scenario is that some CEOs do well for their companies and some do poorly and this doesn't depend on how well they're paid. In other words, I'd vote for possibility 2, except instead of saying CEO pay and company performance are totally random, I'd say they're independent of each other.
And that's not hard to believe. If someone had just a 10% chance of running Exxon 1% more profitably, their market value would be $40 million per year.
More likely explanations: various inefficiencies interfere with getting the best, (good) CEOs are not easily attracted by even larger salaries, companies in dire straits need to pay for the damage they're likely to do to a CEO's resume, the study is simply too small. (Teasing out a 0.01% effect is hard!)
Statistically, the direct effect of CEO pay on the bottom line is dwarfed by the indirect effect of his/her work on the bottom line, making it hard if not impossible to isolate, and so I don't think these numbers quite tell the story you think they do.
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.