The unusual Raman spectrum of MgB$_2$ and its formidable temperature dependence are successfully reproduced by means of a parameter-free emph{ab initio} nonadiabatic theory that accounts for the electron-hole pair scattering mechanisms with the system phonons. This example turns out to be a prototypical case where a strong nonadiabatic renormalization of the phonon frequency is partially washed out by the aforementioned scattering events, bringing along a characteristic temperature dependence. Both electron-hole pair lifetime and energy renormalization effects due to dynamical electron-phonon coupling turn out to play a crucial role. This theory could aid in comprehending other Raman spectra characterized with unconventionally strong electron-phonon interaction.