Non è un problema relativo a Firefox, è un problema che hai causato da solo, nonostante su questo forum più e più volte abbiamo consigliato di non far fare il mestiere di Firefox ad altri software. Il browser può fare pulizia di tutto ciò che è "superfluo" per lui, senza incorrere in problemi come quelli da te citati.
Non è possibile fare nulla da Firefox. Se il programma di pulizia ha usato il tuo cestino allora potrai recuperare qualcosa, diversamente hai perso i tuoi dati. Usando Windows XP posso inoltre dubitare che tu abbia attivato un programma di backup che abbia messo da parte vecchie versioni della cartella del profilo di Firefox, giusto?