Using single-walled carbon nanotubes homogeneously coated with ferromagnetic metal as ultra-high resolution magnetic force microscopy probes, we investigate the key image formation parameters and their dependence on coating thickness. The crucial step of introducing molecular beam epitaxy for deposition of the magnetic coating allows highly controlled fabrication of tips with small magnetic volume, while retaining high magnetic anisotropy and prolonged lifetime characteristics. Calculating the interaction between the tips and a magnetic sample, including hitherto neglected thermal noise effects, we show that optimal imaging is achieved for a finite, intermediate-thickness magnetic coating, in excellent agreement with experimental observations. With such optimal tips, we demonstrate outstanding resolution, revealing sub-10 nm domains in hard magnetic samples, and non-perturbative imaging of nanoscale spin structures in soft magnetic materials, all at ambient conditions with no special vacuum, temperature or humidity controls.