Magnetic Particle Imaging (MPI) is a promising new tracer modality with zero attenuation in tissue, high contrast and sensitivity, and an excellent safety profile. However, the spatial resolution of MPI is currently around 1 mm in small animal scanners. Especially considering tradeoffs when scaling up MPI scanning systems to human size, this resolution needs to be improved for clinical applications such as angiography and brain perfusion. One method to improve spatial resolution is to increase the magnetic core size of the superparamagnetic nanoparticle tracers. The Langevin model of superparamagnetism predicts a cubic improvement of spatial resolution with magnetic core diameter. However, prior work has shown that the finite temporal response, or magnetic relaxation, of the tracer increases with magnetic core diameter and eventually leads to blurring in the MPI image. Here we perform the first wide ranging study of 5 core sizes between 18-32 nm with experimental quantification of the spatial resolution of each. Our results show that increasing magnetic relaxation with core size eventually opposes the expected Langevin behavior, causing spatial resolution to stop improving after 25 nm. Different MPI excitation strategies were experimentally investigated to mitigate the effect of magnetic relaxation. The results show that magnetic relaxation could not be fully mitigated for the larger core sizes and the cubic resolution improvement predicted by the Langevin was not achieved. This suggests that magnetic relaxation is a significant and unsolved barrier to achieving the high spatial resolutions predicted by the Langevin model for large core size SPIOs.