Solución: Puedes liarte a borrar las cookies, el historial, la caché o el disco duro, o puedes usar shift+delete (mayúscula + borrar) sobre la búsqueda en cuestión y eliminarla sin problemas.

Funciona muy bien también para eliminar esos passwords que pusimos mal y que siempre resulta molesto ir acumulando.
Luego de eliminar la búsqueda concreta nos damos cuenta que visitamos una página y en la barra de direcciones al poner una S aparece sadomaso-lol-photos.info . Pues nada, igual que antes podemos borrar esa página del historial pulsando shift+delete.
(Funciona con Firefox, no se si también con IE)

Puede suceder que no recuerdes esas búsquedas problemáticas y que decidas tirar por lo sano, borrar a tu amigo todo su historial de búsquedas:

Borrar búsquedas de Google en Internet Explorer:

1. Ir al menú “herramientas”
2. Seleccionar “opciones de internet”.
3. Selecciona la pestaña “contenido”
4. En la sección “información personal” clicka en “autocompletar”
– Para limpiar el historial actual, dale a “borrar formularios”
– Para deshabilitar totalmente el historial de búsquedas quita la selección de “Formularios”.

Eliminar búsquedas de Google en Firefox:

1. Ir al menú “herramientas”
2. Seleccionar “opciones”
3. Seleccionar la pestaña “privacidad”
4. En la sección “formularios”:
– Para limpiar el historial actual, clicka en “limpiar”.
– Para deshabilitar totalmente el historial de búsquedas quita la selección de “Save information…”.

Puse a google como ejemplo, vale para todos los buscadores y para todos los formularios que almacenan los navegadores.