Stai parando di un account IMAP?
Da quello che hai scritto, sembra che tu abbia già fatto una ricerca e che quindi abbia applicato tutte le soluzioni, ce lo confermi?
Non hai scritto però di avere cancellato gli indici: puoi provare a farlo?
Prima, però, fai sempre un backup dei messaggi di posta, non si sa mai.
Cancellazione degli indici e compattazione delle cartelle (anche più volte consecutivamente) io le farei a programma non in linea; se poi le mail che vuoi cancellare definitivamente sono disponibili in IMAP, sinceramente utilizzerei anche la webmail per sradicare questo persistente problema.