Existem 2 tipos de atalhos no Windows, .lnk e .url. Estes são ambos ocultos a maior parte do tempo, mas sempre que um dos atalhos é quebrado significa que algo mudou, muito provavelmente o arquivo foi movido ou foi excluído.
Além disso, não faça isso:
and even adding that "vistafix" registry thing and restarted my computer,
Se você não sabe EXATAMENTE o que está fazendo, o registro é um mau lugar para se estar. E com a completa falta de detalhes, estou com medo de você.
Quais programas exatamente onde esses atalhos para? Arquivos específicos? As aplicações ainda estão instaladas?
Como os aplicativos estão ausentes, tente isto:
Abra a pesquisa inicial, digite e inicie o Appwiz.cpl. Na barra à esquerda, escolha "Ativar ou desativar recursos do Windows"
Na lista que é preenchida, verifique se "Componentes do Tablet PC" está marcado, se não verificar.
Veja se seus atalhos para esses aplicativos foram restaurados.