Virus de acceso directo y otros

Hola, tengo un problema. Hace unas semanas conecté un dispositivo externo a mi notebook (Windows 7 Starter) lo que provocó que, cuando conecté mis dispositivos (pendrive, mp3 y disco duro), se comenzaron a crear accesos directos, que ocultaban las carpetas originales, pero que al darles clic se abrían, sin problema alguno. De todas formas entenderán que es bastante molesto. Ante esto comencé a buscar soluciones en internet, pero todas aquellas requerían, entre otras cosas, abrir regedit y msconfig, los cuales no me abren, a pesar de que lo he intentado en repetidas ocasiones. También se me ha dicho que ingrese a gpedit.msc, ante lo cual se me abre una ventana emergente que señala que el archivo no se puede encontrar. He intentado instalar distintos antivirus y cleaner como HijackThis y Ccleaner, pero se abre una ventana emergente que dice "Aplication has generated an exception that could not be handled"
Recurro a ustedes porque realmente no sé como borrar este virus, que no sé si está en el notebook o en los usb, no quiero tener que formatear todo :/