Os dois lugares que você mencionou são geralmente os dois lugares em que o software armazenará as chaves:
dados para a máquina local (qualquer usuário) HKEY_LOCAL_MACHINE \ Software
e para o seu perfil específico, seção HKEY_CURRENT_USER \ Software
Uma regra geral para excluir as chaves do registro é fazer o backup primeiro, assim é muito fácil retroceder no caso de você ter alguns efeitos indesejáveis. Observe que a exclusão de chaves do registro pode fazer com que o sistema não inicialize, portanto, tenha muito cuidado com o que você faz, independentemente disso.
Selecione a chave que você está prestes a excluir (por exemplo, Mozilla ou Firefox) no regedit e vá em File > Exportar. Escolha "Filial selecionada" e salve-a em um arquivo. Faça isso para cada chave antes de excluí-la!
Alguns casos pode ser necessário reiniciar para ver as alterações no registro.