Odinstaloval jsi Firefox přes Ovládací panely - Programy? Kontrola v Program Files.
Smazal jsi správnou složku s profilem (viz odkaz)?
Taky všechny složky Mozilla v Data aplikací? V Local a Roaming?

Poslední pokus: Při zavřeném Firefoxu smaž komplet složku s profilem Firefoxu.
Jak ji najdeš je v odkazu výše. Firefox si po spuštění vytvoří nový profil.
Samozřejmě si zálohuj, co jsem psal prve.