Via computational modeling, we investigate the mechanism of strain recovery in dual cross-linked polymer grafted nanoparticle 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 long time. We show that this rejuvenation depends on the fraction of permanent bonds, strength of labile bonds, and maximal strain. 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 not only enables faster recovery but also yields improved recovery even after multiple stretch-relaxation cycles. © 2013 The Royal Society of Chemistry.