Small-angle neutron scattering experiments on nanostructured Fe, Co, and Ni reveal grain-size dependent magnetic correlations across grain boundaries. In Fe, a minimum of the correlation length is observed for grain sizes of the order of the bulk domain-wall width where the coercive field has a maximum. The results are explained within a generalization of the random-anisotropy model that takes into account domain-wall formation within grains and reduced interface coupling.