Não posso dizer que não tenha trapaceado para obter a resposta. Todos os créditos vão para morguth para o seu post aqui .
O que ele sugeriu (e provou funcionar no meu Win7 e XPMode) é que existe uma chave de registro que força o shell a reiniciar automaticamente. Ao usar o seguinte código, você desativa isso.
RegistryKey ourKey = Registry.LocalMachine;
ourKey = ourKey.OpenSubKey(@"SOFTWARE\Microsoft\Windows NT\CurrentVersion\Winlogon", true);
ourKey.SetValue("AutoRestartShell", 0);
// Kill the explorer by the way you've post and do your other work
ourKey.SetValue("AutoRestartShell", 1)