Pulsed-laser-induced quenching of ferromagnetic order has intrigued researchers since pioneering works in the 1990s. It was reported that demagnetization in gadolinium proceeds within 100 ps, but three orders of magnitude faster in ferromagnetic transition metals such as nickel. Here we show that a model based on electron-phonon-mediated spin-flip scattering explains both timescales on equal footing. Our interpretation is supported by ab initio estimates of the spin-flip scattering probability, and experimental fluence dependencies are shown to agree perfectly with predictions. A phase diagram is constructed in which two classes of laser-induced magnetization dynamics can be distinguished, where the ratio of the Curie temperature to the atomic magnetic moment turns out to have a crucial role. We conclude that the ultrafast magnetization dynamics can be well described disregarding highly excited electronic states, merely considering the thermalized electron system.