We study the spontaneous emission of atoms coupled to frequency-dependent photon-mode reservoirs, and find atomic emission spectra qualitatively different from those of free space. Frequency-dependent photon-mode reservoirs are found in a variety of physical situations (e.g., in waveguides, microcavities, dielectrics, systems with photonic spectral gaps, etc.), and are shown to lead to nonexponential decay and concomitant complicated non-Lorentzian emission line shapes. By studying Autler-Townes spectra in the presence of a frequency-dependent photon-mode density, we present simple examples of dynamical modifications of spontaneous decay properties.