Teóricamente con la opción de "Eliminar todo" se eliminan todos los retos de navegación locales. Para más seguridad puedes usar el CCleaner que limpia tambiéne los formularios, el index.dat, etc

CCleaner:
http://www.piriform.com/ccleaner/features


Creo que no hay ninguna clave del registro de Windows que guarde caché o información de navegación. Pero si estás navegando detrás de un proxy (en el trabajo por ejemplo), por mucho que borres el historial sabrán perfectamente dónde entras.