Es lo malo de Gmail, que no funciona por carpetas sino por etiquetas. Es un IMAP personalizado y propio de ellos.
Te puede estar pasando que cuando envías el comando IMAP de borrar, lo que hace es añadir la etiqueta "deleted", pero no quita la de "inbox".
Cuando hagas lo de siempre de borrar, ve a al interfaz web y comprueba qué etiquetas tiene ese correo que acabas de eliminar. Si tiene otra además de la de eliminar, deberás mirar a ver si tienes algún filtro o algo que le asigne una etiqueta adicional a los mensajes de entrada.
Estoy suponiendo que sea este el problema, porque anda que no me dio quebraderos de cabeza en su día... cuando movía correos de una carpeta a otra. No sé si hacía lo de borrar o que, pero desde hace la tira yo los muevo, paso de los maniqueos que haga el servidor para que encaje en la interfaz web y sus etiquetas.
Creo recordar que el problema está en la asignación de la carpeta de eliminados por parte de los clientes de correo. Normalmente está en la raíz "Trash", pero Google la tiene en "Gmail/Trash". Una solución es asignar a la carpeta el rol de Trash, si lo tiene erróneamente asignado (no me preguntes cómo se hace en 365), pero 365 debería de asignarla correctamente, supongo..., otra cosa son clientes de uso más tradicional.
Mira si realmente te los mueve a la papelera en la interfaz web.
P.S.: Perdón por la parrafada, pero era algo así y me ido acordando según lo escribía.
