Laser pulses traveling through a plasma can feature group velocities significantly differing from the speed of light in vacuum. This modifies the well-known Volkov states of an electron inside a strong laser-field from the vacuum case and, consequently, all quantum electrodynamical effects triggered by the electron. Here we present an in-depth study of the basic process of photon emission by an electron scattered from an intense short laser pulse inside a plasma, labeled nonlinear Compton scattering, based on modified Volkov solutions derived from first principles. Consequences of the nonlinear, plasma-dressed laser dispersion on the Compton spectra of emitted photons and implications for high-intensity laser-plasma experiments are pointed out. From a quantitative numerical evaluation we find the plasma to effectively suppress emission of low-frequency photons, whereas the emission of high-frequency photons is enhanced. The emission's angular distribution, on the other hand, is found to remain qualitatively unchanged with respect to the vacuum case.