Explorador de Windows dice que no encuentra el archivo

Hola a todos. Normalmente no hago preguntas y mucho menos sin antes haber investigado bastante. También soy experto en varias categorías pero este problema me tiene sin aliento.
Desde hace unos días cuando quiero abrir algunos programas me sale un mensaje de que "Windows no puede encontrar el archivo". Aclaro, NO es un acceso directo, si lo fuera mostraría la opción de buscar manualmente el destino o en su defecto la de eliminar el acceso directo. Esto me pasa cuando doy doble click en el archivo directamente desde el disco duro. Me ha sucedido con Microsoft Office (todas las aplicaciones Office) y más recientemente con Skype. El Office se arregló con la reinstalación pero el Skype no.

Ésto es más o menos lo que he probado:
1. Reinstalar el programa.
2. Ejecutar en varios modos de compatibilidad.
3. Desinstalar limpiamente el programa, reparar errores con CCleaner y reinstalar.
4. Reinstalar en un directorio diferente.
5. Buscar actualizaciones.
6. Activar el inicio automático de Skype.
7. Reiniciar el computador.

Se supone que instalarlo en otra carpeta debería arreglar cualquier problema relacionado con el registro de Windows, ya que sería una entrada totalmente nueva y diferente pero no ha funcionado. Puedo desintalar la aplicación sin contratiempos, en su lugar, también me sucede el conflicto con McAfee Security Scan que por cierto, se instaló sin que me diera cuenta y ahora no puedo desinstalar. Windows dice que el programa ya fue desinstalado, CCleaner dice que no encuentra el archivo y TuneUp Uninstaller se cuelga al tratar de hacer lo mismo.

Dejo una captura de pantalla para que puedan ver mejor de lo que estoy hablando. Aclaro nuevamente: No es un acceso directo. Pueden ver la ruta completa de la instalación recién terminada.

Antes lo tenía en "C:\Archivos de programa (x86)\Skype\Phone" (ruta por defecto)
luego en "C:Archivos de programa\Skype\Phone" (Sin x86 para probar solamente)
luego en C:\Archivos de programa (x86)\Skype_re\Phone" (nótese el "_re" para variar de directorio)
finalmente en la ubicación de la captura "D:\Skype\Phone"

Se puede ver claramente el sistema operativo Windows 8.1 de 64 bits lo cual no tiene nada que ver con el problema ya que antes funcionaba bien.

Intel Core i3
Memoria RAM 4GB
Disco duro 1TB
Gráfica integrada Intel HD 4000

Finalmente, como mencioné al principio, he luchado bastante con este problema antes de hacer la pregunta así que por favor respondan con seriedad. Un experto recién registrado intentó ayudar diciéndome que hiciera limpieza de virus y malware. Le respondí a su publicación diciéndole que nada de eso serviría pero aun así lo haría. En efecto, lo único que apareció fueron unos cuantos cracks y keygens que siempre se reconocen como maliciosos sin serlo. El usuario nunca respondió de vuelta y por eso publico nuevamente la pregunta.

Si se abre la imagen en otra pestaña se puede ver de tamaño completo.