Outlook Express no borra los mensajes que eliminamos.
Para eliminarlos definitivamente:
Ir a [Inicio] [Buscar] [Archivos o Carpetas] y buscamos la palabra "elementos". El resultado será "Elementos Eliminados.dbx", pulsamos el botón derecho del mouse y clic sobre [Eliminar].
Para Windows XP: antes de realizar la búsqueda hay que seleccionar [Mas opciones avanzadas] y marcar la casilla [Archivos y carpetas ocultos].