Using a sub-millimetre sized YIG (Yttrium Iron Garnet) sphere mounted in a magnetic field-focusing cavity, we demonstrate an ultra-high cooperativity of $10^5$ between magnon and photon modes at millikelvin temperatures and microwave frequencies. The cavity is designed to act as a magnetic dipole by using a novel multiple-post approach, effectively focusing the cavity magnetic field within the YIG crystal with a filling factor of 3%. Coupling strength (normal-mode splitting) of 2 GHz, (equivalent to 76 cavity linewidths or $0.3$ Hz per spin), is achieved for a bright cavity mode that constitutes about 10% of the photon energy and shows that ultra-strong coupling is possible in spin systems at microwave frequencies. With straight forward optimisations we demonstrate that with that this system has the potential to reach cooperativities of $10^7$, corresponding to a normal mode splitting of 5.2 GHz and a coupling per spin approaching 1 Hz. We also observe a three-mode strong coupling regime between a dark cavity mode and a magnon mode doublet pair, where the photon-magnon and magnon-magnon couplings (normal-mode splittings) are 143 MHz and 12.5 MHz respectively, with HWHM bandwidth of about 0.5 MHz. ; Comment: appears in Phys. Rev. Applied (2014)