Часто, это делают преднамеренно, например, в триальных программах. Удалил, когда пробный период закончился, ставишь по новой... и досвидос.
Очень трудно находить эти записи в реестре - они, обычно, никак не связаны с названием программы. Причём, их может быть несколько.
Ну, а про остальное, выше уже отписались.
Что бы полностью удалить, нужно перед установкой делать снимок реестра, после запуска программы второй и хранить это дело - при удалении, практически 100 процентов будет удалено. Есть утилиты, которые это делают автоматом. Например, RegOrganizer.
Кстати, обычные "удалялки", тоже не всё полностью удаляют.
Если есть желание просто попробовать какую программу, то для этого есть утилита Shadow Defender. После перезагрузки получаешь ось в том состоянии. которое было до запуска этой утилиты. Очень полезная штука.