We study the depolarization dynamics of a dense ensemble of dipolar interacting spins, associated with nitrogen-vacancy centers in diamond. We observe anomalously fast, density-dependent, and nonexponential spin relaxation. To explain these observations, we propose a microscopic model where an interplay of long-range interactions, disorder, and dissipation leads to predictions that are in quantitative agreement with both current and prior experimental results. Our results pave the way for controlled many-body experiments with long-lived and strongly interacting ensembles of solid-state spins.