The temperature dependence of the electron spin relaxation time in MgB2 is anomalous as it does not follow the temperature dependence of the resistivity above 150 K, it has a maximum around 400 K, and it decreases for higher temperatures. This violates the well established Elliot-Yafet theory of electron spin relaxation in metals. We show that the anomaly occurs when the quasi-particle scattering rate (in energy units) becomes comparable to the energy difference between the conduction- and a neighboring band. We find that the anomalous behavior is related to the unique band structure of MgB$_2$ and the large electron-phonon coupling. The saturating spin-lattice relaxation can be regarded as the spin transport analogue of the Ioffe-Regel criterion of electron transport.