Why is Mauna Kea taller than the maximum height possible on Earth? We can calculate the maximum possible height of the mountain on earth. 
If the elastic limit of a typical rock is $3 \times 10^8\ \mathrm{N/m}$ and its mean density is $3 \times 10^3\ \mathrm{kg/m^3}$, then the breaking stress is $h\,\rho\,\mathrm{g}$, where $h$ is height, $\rho$ is the density of the rock, and $\mathrm{g}$ is the acceleration due to gravity. Then

$$ h = \frac{\mathrm{elastic\ limit}}{\rho\,\mathrm{g}} $$

Putting the values we get,

$$ h = 10^4\ \mathrm{m} $$

which is the maximum possible height. Now Mount Everest is within this limit, but Mauna Kea is 10,210 m tall (measured from its oceanic base).

Does this suggest that rock types at the base of this mountain are different?
Or does the presence of water have an effect?
Since over half of the height of Mauna Kea is under water, you need to consider the buoyancy effect. Instead of a density of $3 \times 10^3\ \mathrm{kg/m^3}$, the underwater portion has a net density of $2 \times 10^3\ \mathrm{kg/m^3}$. That will significantly increase the potential height of such a mountain. Add in all the other uncertainties (is Mauna Kea made of rock with &quot;typical&quot; elastic limit and density? is it even homogenous? are there dynamics involved? and what about Naomi?) and there's no reason to see its height as a contradiction.