A pair of Auger electrons generated, respectively, by creation and annihilation of the same multiple-hole state can be collected in coincidence by Auger Auger-electron coincidence spectroscopy (AAECS). In the present paper a many-body theory of AAECS spectra generated by Auger cascade decays in which the lifetime of a core-hole acts as an internal clock for the screening mechanism is formulated by treating photoelectrons and Auger electrons on the same footing. The unexploited basic spectral features of AAECS spectra of solids are elucidated by the present theory to show how the core-hole screening (delocalization of a valence hole) will affect the coincidence spectral lineshape.