No hagas nada con ese ordenador. No navegues, no instales software en ese disco duro, etc. Cualquier fichero nuevo (temporales de internet incluidos) puede sobreescribir la información que te interesa recuperar.
Si tienes la opción, lo ideal es que desconectes ese disco duro y lo conectes en otro equipo como secundario. Y en el principal de ese otro equipo instales RECUVA y hagas una búsqueda profunda sobre el disco donde estaban los ficheros.
En las opciones de recuperación, si te encuentra esos ficheros que buscas, le dices que te los restaure en el disco principal, y SOLO los pases al otro una vez estés seguro que tienes lo que quieres. Después ya puedes poner todo en su sitio.