@OOQQ, está hablando de mensajes RECIBIDOS en respuesta a unos suyos, no enviados.
EDIT: y, por cierto, ahora que recuerdo, Gmail guarda copia de todos los mensajes que pasan por su servidor SMTP, o sea, si el que buscase fuera un mensaje enviado desde un cliente de correo TAMBIÉN estaría en el servidor.
@juan66bcn, si no los borraste siguen estando en el servidor. Gmail no borra nada automáticamente salvo de la carpeta papelera o spam.
Así que, si no los borraste, usa el buscador de mensajes que tiene la propia interfaz web de Gmail. Si no sale, es que lo borraste y punto.
Olvídate de usar un cliente de correo IMAP porque no deja de ser un acceso desde un programa, en vez de desde la web, a las carpetas que existen en el servidor.
EDIT: añado, sólo en el caso de que te bajaras los correos con un cliente de correo POP e indicases que se borraran del servidor al descargar habrían desaparecido del servidor, pero quedarían en las carpetas de ese programa.
Pero entiendo que este no es tu caso, sólo lo aclaro.