We theoretically investigate spin-dependent carrier dynamics due to the electron-phonon interaction after ultrafast optical excitation in ferromagnetic metals. We calculate the electron-phonon matrix elements including the spin-orbit interaction in the electronic wave functions and the interaction potential. Using the matrix elements in Boltzmann scattering integrals, the momentum-resolved carrier distributions are obtained by solving their equation of motion numerically. We find that the optical excitation with realistic laser intensities alone leads to a negligible magnetization change, and that the demagnetization due to electron-phonon interaction is mostly due to hole scattering. Importantly, the calculated demagnetization quenching due to this Elliot-Yafet-type depolarization mechanism is not large enough to explain the experimentally observed result. We argue that the ultrafast demagnetization of ferromagnets does not occur exclusively via an Elliott-Yafet type process, i.e., scattering in the presence of the spin-orbit interaction, but is influenced to a large degree by a dynamical change of the band structure, i.e., the exchange splitting.