Transverse NMR relaxation from spins diffusing through a random magnetic medium is sensitive to its structure on a mesoscopic scale. In particular, this results in the time-dependent relaxation rate. We show analytically and numerically that this rate approaches the long-time limit in a power-law fashion, with the exponent reflecting the disorder class of mesoscopic magnetic structure. The spectral line shape acquires a corresponding non-analytic power law singularity at zero frequency. We experimentally detect a change in the dynamical exponent as a result of the transition into a maximally random jammed state characterized by hyperuniform correlations.