Abre el explorador, arriba en el menú vete a herramientas, Opciones de internet y elige la pestaña de contenido. En la ficha de información personal, dale al botón autocompletar y deselecciona la casilla de "Autocompletar para direcciones Web" con eso ya no se te van a almacenar en la barra de direcciones.
Con eso y borrando el historial creo que ya debería valer.