Si a raíz de una infección vírica se han borrado los accesos directos de Menú Inicio\Todos los programas en Windows 7/Vista y/o los iconos de acceso directo del escritorio de todos los usuarios (antiguo All Users, ahora Public), probar lo siguiente:

1) Que la carpeta AppData\Local\Temp\smtmp\1\ dentro de la cuenta de nuestro usuario (C:\Users\Usuario\AppData\Local\Temp\smtmp\1\) existe y tiene todas las carpetas y accesos directos del Todos los programas

2) Que la carpeta AppData\Local\Temp\smtmp\4\ dentro de la cuenta de nuestro usuario (C:\Users\<Usuario>\AppData\Local\Temp\smtmp\4\) existe y tiene los elementos del escritorio público.

Si es así, sólo queda restaurarlos. La forma más rápida es abrir una ventana de comando con permisos de Administrador (ojo con esto) y tirar de Xcopy:

xcopy %Temp%\smtmp\1 «C:\ProgramData\Microsoft\Windows\Start Menu» /H /I /S /Y /C

xcopy %Temp%\smtmp\4 «C:\Users\Public\Desktop» /H /I /S /Y /C

El bicho en cuestión también había hecho desaparecer todo lo existente en Users. En casos como ese es importante no dejarse llevar por el pánico. Puede haberlos ocultado o convertido en archivos de sistema. El comando Attrib es de gran ayuda en estos casos. Como antes, siempre ejecutando la consola en modo administrador.