You have the recovery discs and trust they'll work, then OK let's really clean that laptop.
Google for either KILLDISK or DBAN, find the .ISO file and burn to a disc. Reboot with the burnt disc and follow the prompts to really wipe out the old data, etc.. Once done, then do an OS re-install but also a proper reformat during that install and it should reload back to day 1. HOWEVER, if your recovery discs were made some time after you had the laptop, you may have created a " dated image" of that laptop so you can return to it as in restore to that date. You state you have recovery disc(s), basically how were these made, if not factory supplied. It's important to note that those recovery discs if user made need to be reliable so you can retrun to a working laptop, otherwise a real wipe out will totally make it secure until a proper OS reload is done. Details, details they matter.
BTW, doesn't Recuva rescue or do repair of files, if so you may have unshred files, it may have repaired them. Just a WAG on that, but recheck use setting.