The spin relaxation time in solids is determined by several competing energy scales and processes, and distinct methods are called for to analyze the various regimes. We present a stochastic model for the spin dynamics in solids which is equivalent to solving the spin Boltzmann equation and takes the relevant processes into account on an equal footing. The calculations reveal yet unknown parts of the spin-relaxation phase diagram, where strong reversible spin dephasing occurs in addition to spin relaxation. Spin-relaxation times are obtained for this regime by introducing the numerical Loschmidt echo. This allows us to construct a generic approximate formula for the spin-relaxation time, tau(s), for the entire phase diagram, involving the quasiparticle scattering rate, Gamma, spin-orbit coupling strength, L, and a magnetic term, Delta(Z) due to the Zeeman effect. The generic expression reads as (h) over bar /t(s) approximate to L-2/(Gamma(2) + L-2 + Delta(2)(Z)).