Javier Enrique, por mi parte sólo se ocurre que tu instalación de Windows tenga una serie de errores de indexación de archivos, no es algo usual pero a veces ocurre, este error provoca una aparente perdida de datos que en realidad es falsa, pues los archivos estan ahí, no fueron eliminados. No sé corregirlo pero puedes ver enlaces dode explican posibles soluciones
http://windows.microsoft.com/es-es/windows7/open-the-search-and-indexing-troubleshooter
http://www.hispasonic.com/foros/si-os-desaparecen-carpetas-golpe-windows/312646
El segundo posible motivo es más habitual, se trata de la acción de un virus o malware que altera el funcionamiento de Windows, aquí tampoco tengo un conocimiento de cómo solucionarlo, pero de nuevo, mientras otra persona te contesta puedes ver algunas formas de intentar afrontarlo desde estas páginas
https://www.youtube.com/watch?v=ub7DoMqf2Ts
http://es.kioskea.net/forum/affich-479866-eliminar-virus-que-oculta-carpetas
http://www.forospyware.com/t471555.html
Además puedes pasar programas antimalware (bots, troyanos) que detectan y eliminan virus/bots que no son identificados normalmente por el antivirus, estos programas pueden ser por ejrmplo MalwareBytes o Hijackthis entre otros, a ver si tenemos suerte.
https://www.malwarebytes.org/mwb-download/
http://sourceforge.net/projects/hjt/
Existen otros programas muy parecidos a Recuva (reuperación de datos), como Glary Utilities o TestDisc, pero es dificil que funcionen cuando Recuva no ha consiguido recuperarlos, siento ser pesimista en ese sentido.