Adressen im Explorer löschen sich automatisch nach Neustart. Wie ändern ?

Erste mögliche Variante: Der Verlauf ist auf 0 Tage gesetzt (unter Internetoptionen im IE).
Ich weiß, du meinst eigentlich nicht den Verlauf, womöglich liegt es trotzdem daran.

Zweite Variante:
In der Autostartgruppe ist ein Befehl bzw. eine Datei vorhanden, die dafür sorgt, dass die Temporary Internet Files (TIF) (+ event. auch Verlauf und Cookies) vor dem Start der Windows-Oberfläche gelöscht werden.

Lösung:
msconfig starten (Start -> Ausführen -> msconfig)
Dort nach "verdächtigen" Einträgen suchen.
Eine mögliche Variante wäre zB ein Eintrag, der eine Datei namens Purge.cmd startet.
Was es genau mit dieser Datei auf sich hat, liest du am besten einmal hier nach: klick!
Die sorgt nämlich dafür, dass eben TIF, Cookies und Verlauf vor dem eigentlich Start der Windows-Oberfläche gelöscht werden.

Falls du einen derartigen Eintrag findest -> lösch ihn.

Das Problem in XP ist, dass die eigentlich Angaben der TIF in einer index.dat gespeichert sind, die man so ohne Weiteres nicht löschen kann.
Wobei in deinem Falle das Problem ja eher umgekehrter Natur ist: Die Einträge werden gelöscht, obwohl du das eigentlich nicht möchtest.

Wie gesagt: Am besten zuerst den Link studieren, dementsprechend dein System durchsuchen und bei erfolgreicher Suche den entsprechenden Eintrag löschen.

Ansonsten: hier weiterfragen.

So long....