Via computational modeling, we investigate the mechanism of strain recovery in dual cross-linked polymer grafted nanoparticle (PGN) networks. The individual nanoparticles are composed of a rigid spherical core and a corona of grafted polymers that encompass reactive end groups. With the overlap of the coronas on adjacent particles, the reactive end groups form permanent or labile bonds, and thus form a “dual cross-linked” network. We consider the strain recovery of the material after it is allowed to relax from the application of a tensile force. Notably, the existing labile bonds can break and new bonds can form in the course of deformation. Hence, a damaged material could be “rejuvenated” both in terms of the recovery of strain and the number of bonds, if the relaxation occurs over a sufficiently longtime. We show that this rejuvenation depends on the fraction of permanent bonds and strength of labile bonds. Specifically, we show that while an increase in the labile bond energy leads to formation of a tough material, it also leads to delayed strain recovery. Further, we show that an increase in the fraction of permanent bonds yields improved recovery even after multiple stretch-relaxation cycles.