Fico feliz em saber que você resolveu seu problema. Se, no futuro, você quiser um método menos complicado de fazer isso, pode pegar o CCleaner .
Além de ser um aplicativo de limpeza de disco extremamente útil, ele tem a opção de facilmente eliminá-los também - no grupo Avançado, marque "Tray Notifications Cache" e depois clique em "Run Cleaner". Você ainda terá que reiniciar o explorer.exe, mas é um pouco mais rápido do que circunavegar o Registro. :)