We investigate the effect of Ho, Dy, Tb, and Gd impurities on the femtosecond laser-induced magnetization dynamics of thin Permalloy films using the time-resolved magneto-optical Kerr effect. Varying the amount of Ho, Dy, Tb content from 0% to 8%, we observe a gradual change of the characteristic demagnetization time constant from approximate to 60 to approximate to 150 fs. In contrast, Gd concentrations up to 15% do not influence the time scale of the initial photoinduced magnetization loss. We propose a demagnetization mechanism that relies on strong magnetic inertia of the rare-earth dopant which stabilizes the ferrimagnetic ordering and thereby delays the demagnetization.