Как полностью удалить FF с машины?
т.е. чтобы неосталось абсолютно никаких следов от того что он там был, чтобы потом его заново поставить.

Я удаляю его из "Установки и удаления программ", папки c:\Program Files\Mozilla Firefox , c:\Documents and Settings\...\Application Data\Mozilla.
Но видимо где-то еще следы остаются, т.к. он например помнит из какой папки в последний раз открывался файл...

HL-Man
Еще есть реестр.

Их два.
C:\Documents and Settings\Igor Comp\Application Data\Mozilla
C:\Documents and Settings\Igor Comp\Local Settings\Application Data\Mozilla