En el momento en el que decides eliminar el historial (u otro tipo de archivos temporales) le estás indicando al navegador que debe deshacerse definitivamente de esos datos, o dicho de otro modo, que no debe seguir guardándolos en ningún sitio, por ende, se vuelve irrecuperable, ya que la información deja de existir.

Si estuvieramos hablando de archivos temporales que se almacenan en archivos individuales que son reemplazados (eliminando el archivo antiguo/temporal), pues todavía podrías tener alguna posibilidad con cualquier aplicación de recuperación de datos (ej. Recuva) para restaurar "versiones" anteriores de los archivos eliminados, pero no es el caso, de todas formas te diré que Mozilla Firefox almacena el historial, cifrado, en el archivo places.sqlite, y Google Chrome en el archivo History (sin extensión), sobre el Opera no tengo ni idea pero con una búsqueda en Google lo encontrarías facilmente.

Por último, me gustaría indicarte que la herramienta más completa de análisis forense de actividad de navegación, historiales, etc, es Net Analysis:

• http://www.digital-detective.net/digital-forensic-software/netanalysis/

...Aunque hay otras aplicaciones mucho más simples (y gratuitas) como es BrowsingHistoryView para el único fin que te interesa, observar el historial.

• http://www.nirsoft.net/utils/browsing_history_view.html

Saludos