Возможно уже стало теплее. Я экспортировал с пострадавшей машины раздел реестра: HKEY_LOCAL_MACHINE\SOFTWARE на внешний носитель. На другом, абсолютно здоровом компе запустил VMWare и установил на виртуалку свежий WinXP SP3. Далее импортировал этот раздел реестра и после перезагрузки там тоже пропал эксплорер, но вместе с этим всплыли пара ошибок, которые возможно проливают свет на проблему (смотрите на скрины):
Обратите внимание что на виртуалке стояла свежая WinXP SP3 без установленного софта. Перенес только раздел реестра и там тоже начались проблемы с эксплорером!
Вот думаю, может удалить в реестре все упоминания об explorer.exe, может запрет или блокировка снимется?