Какая Винда? SP? Такой баг действительно наблюдается при сносе антивируса (бывает с Norton и др.).
Прежде всего проверь остались ли записи о деинсталляторах в реестре:
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Uninstall
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\App Management\ARPCache
Если нет, то дело совсем плохо и здесь поможет только откат (Восстановление системы), конечно если нет резервной копии ключей. К тому же по идее не работало бы удаление из папок в меню "Пуск"... Хотя не обязательно.
Предлагаю попробовать следующие варианты:
1. Откат к ближайшей точке;
2. Прога наподобие
WinDoctor из Systemworks (чистильщик реестра);
3. Команда
sfc /scannow;
4. Скопируй из дистрибутива
appwiz.cpl в папку
WINDOWS\system32, заменив прежний.
P.S. Проблема
действительно интересная! Решения, к сожалению, по-прежнему не найдено.