Eliminar registro de búsquedas de Google

Google, no tiene ningún registro.
Es tu navegador el que almacena un historial de páginas visitadas y de lo que escribes en los formularios.
Busca en las Opciones/Preferencias, y elige lo que quieres que recuerde, o bórralo todo.

Si, es posible con una herramienta que esta destinada a quitar programas espías y publicitarios de las pc, el programa detecta también las listas de direcciones de internet, últimos archivos ejecutados, las direcciones de google en si todo el historial, y deja tu pc como si nadie la hubiese usado, es gratis se llama Ad-Aware SE, lo pillas aquí:
www.download.com
Y el parche para español esta aqui:
www.lavasoft.com bajo downloads encontraras la descargua del LANGUAGE PACK.

Con lo que te he dicho, debe funcionar, por si acaso, borra las cookies, los archivos descargados, y así si que no debes de tener nada en el historial!...

Tienes un montón de programas para hacer eso, o editando el registro...
La más fácil que es la que te recomiendo es que bajes el programa hijack recovery con eso borras todos los rastros del internet explorer...
Suerte!