Hola, mi nombre es Héctor, usuario de Microsoft; estaré feliz de ayudarte hoy.
Lamento que tengas este problema.
Para borrar el historial de búsqueda de Outlook te recomiendo seguir las instrucciones del siguiente artículo oficial de Microsoft:
Mantenme al tanto del resultado para continuar el acompañamiento.
Si la información proporcionada te ha sido de utilidad no dudes de dar tu opinión para que otros usuarios con la misma inquietud puedan aclararla.