Leo en el blog de Luis Ignacio Díaz del Dedo que Gmail no borra los mails que sí marcas tú para eliminar y que ya no se encuentran en la papelera. Quien habla de Gmail, habla de Google Apps y por lo tanto, multitud de dominios de particulares y empresas sufrirán el mismo problema. Lo comprobó cuando al sincronizar el correo con un nuevo equipo, se le descargaron mails de 2006 cuando el más antiguo era de 2008 (según aparecía en su cuenta a través del interfaz web).

Si es cierto lo que dice y el problema lo ha sufrido más gente, puede ser verdad que Google no elimine los mails que tienes en teoría eliminados. ¿Hasta qué punto puede suponer un problema? Quizás a casi nadie le afecte directamente, pero dado que el correo es algo privado, se está "atentando" contra tu privacidad y es algo que debemos por lo menos de tener en cuenta.

De todas maneras, no creo que el resto de las compañías se comporten de manera muy distinta y creo que a la larga, por ahorro de Google incluso, le conviene borrar los mails. Los sistemas de correo como Gmail son tan enormes que dicho comportamiento puede ser un error puntual debido a la recuperación de un backup o algo similar, que en un centro de sistemas como el que use Google, tiene que ser algo habitual.

Aún así, sigo creyendo que Gmail es el mejor servicio de correo disponible en la actualidad.