Lo primero es intentar no bajar más datos, pues estos podrían ocupar el espacio físico donde se albergaban los archivos que fueron borrados. Lo segundo es revisar si efectivamente ya no existen, en caso de que sea así pues acudir a algún software gratuito de recuperación.
Si se tiene la oportunidad de acceder al disco duro a través de un sistema linux mucho mejor (para ver realmente el contenido del disco duro que podría estar oculto o bloqueado por algún virus de windows)