While typical theories of atom-light interactions treat the atomic medium as being smooth, it is well-known that microscopic optical effects driven by atomic granularity, dipole-dipole interactions, and multiple scattering can lead to important effects. Recently, for example, it was experimentally observed that these ingredients can lead to a fundamental, density-dependent dephasing of optical spin waves in a disordered atomic medium. Here, we go beyond the short-time and dilute limits considered previously, to develop a comprehensive theory of dephasing dynamics for arbitrary times and atomic densities. In particular, we develop a novel, non-perturbative theory based on strong disorder renormalization group, in order to quantitatively predict the dominant role that near-field optical interactions between nearby neighbors has in driving the dephasing process. This theory also enables one to capture the key features of the many-atom dephasing dynamics in terms of an effective single-atom model. These results should shed light on the limits imposed by near-field interactions on quantum optical phenomena in dense atomic media, and illustrate the promise of strong disorder renormalization group as a method of dealing with complex microscopic optical phenomena in such systems.