We perform a detailed study of the location of brightest cluster galaxies (BCGs) on the Fundamental Plane of black hole (BH) accretion, which is an empirical correlation between a BH X-ray and radio luminosity and mass supported by theoretical models of accretion. The sample comprises 72 BCGs out to z similar to 0.3 and with reliable nuclear X-ray and radio luminosities. These are found to correlate as L-X alpha L-R(0.75 +/- 0.08), favouring an advection-dominated accretion flow as the origin of the X-ray emission. BCGs are found to be on average offset from the Fundamental Plane such that their BH masses seem to be underestimated by the M-BH-M-K relation a factor similar to 10. The offset is not explained by jet synchrotron cooling and is independent of emission process or amount of cluster gas cooling. Those core-dominated BCGs are found to be more significantly offset than those with weak core radio emission. For BCGs to on average follow the Fundamental Plane, a large fraction (similar to 40 per cent) should have BH masses > 10(10) M-circle dot and thus host ultramassive BHs. The local BH-galaxy scaling relations would not hold for these extreme objects. The possible explanations for their formation, either via a two-phase process (the BH formed first, the galaxy grows later) or as descendants of high-z seed BHs, challenge the current paradigm of a synchronized galaxy-BH growth.