We present a measurement-cost efficient implementation of Strongly-Contracted (N)-Electron Valence Perturbation Theory (SC-NEVPT2) for use on near-term quantum devices. At the heart of our algorithm we exploit the properties of adaptive Informationally Complete positive operator valued measures (IC-POVMs) to recycle the measurement outcomes from a ground state energy estimation on a quantum device to reconstruct the matrix elements of the three- and four-body reduced density matrices for use in a subsequent CPU-driven NEVPT2 calculation. The proposed scheme is capable of producing results in good agreement with corresponding conventional NEVPT2 simulations, while significantly reducing the cost of quantum measurements and allowing for embarrassingly parallel estimations of higher-order RDMs in classical post-processing. Our scheme shows favourable scaling of the total number of shots with respect to system size. This paves the way for routine inclusion of dynamic electron correlation effects in hybrid quantum-classical computing pipelines.