A solid-state single-photon source emitting indistinguishable photons on-demand is an essential component of linear optics quantum computing schemes. However, the emitter will inevitably interact with the solid-state environment causing decoherence and loss of indistinguishability. In this paper, we present a comprehensive theoretical treatment of the influence of phonon scattering on the coherence properties of single photons emitted from semiconductor quantum dots. We model decoherence using a full microscopic theory and compare with standard Markovian approximations employing Lindblad-type relaxation terms. Significant differences between the two approaches are found.