Il fatto che ti ricompaiano mi sembra molto strano.
Comunque la "cronologia" è una cosa, la history del menu a tendina nella barra delle applicazioni è un'altra, e non hanno nulla a che fare tra di loro.

La prima si trova nella cartella "Cronologia" della cartella "\Windows" (se usi win9x) oppure nella cartella "C:\Documents and Settings\Nome utente\Impostazioni locali\Cronologia" (se usi winXP o Win2000)


Per quando riguarda invece gli url digitati e presenti nella barra li trovi nel registro di sistema nella seguente chiave

codice:
HKEY_CURRENT_USERS\Software\Microsoft\ Internet Explorer\TypedURLS
Lì puoi cancellare selettivamente le chiavi che vuoi eliminare.
Ovviamente ti ricordo di fare molta attenzione... si possono fare parecchi danni nel registro di sistema!


Un'altra nota: se vuoi si puo' eliminare totalmente la memorizzazione degli url nella barra con dalle Opzioni Internet selezionando la cartellina "contenuto", pulsante "completamento automatico" e togliendo le spunte dalle voci appropriate.