We study the fundamental limit on single-photon indistinguishability imposed by decoherence due to phonon interactions in semiconductor quantum dot-cavity QED systems. Employing an exact diagonalization approach we find large differences compared to standard methods. An important finding is that short-time non-Markovian effects limit the maximal attainable indistinguishability. The results are explained using a polariton picture that yields valuable insight into the phonon-induced dephasing dynamics.