Máš poradnu v záložkách? Pokud ano, tak máš možná zaškrtlé políčko úplně nahoře v dialogovém okně "Odstranit historii procházení", je tam něco ve smyslu "Chránit data oblíbených webových položek".
Je to IMHO to, že sušenky z oblíbených webů to data nevymaže. Po reinstalu jsem to měl taky tak, vymazal jsem data, ale po opětovném spoštění IE jsem byl přihlášen. Po odškrtnutí tohoto políčka to bylo vyřešeno.