Se as mensagens já tiverem sido excluídas, você já tentou compactar as pastas ?
Como a página afirma:
... switch to working offline using File -> Offline -> Work Offline, select an account and then manually compact the folders in that account using File -> Compact Folders instead. You can also compact a specific folder by right clicking on it and selecting "Compact" from the context menu:
YouhaveseveraladditionaloptionsifyouareusingaIMAPaccount.IfyoucheckTools->AccountSettings->ServerSettings->Cleanup("Expunge") Inbox on Exit it will compact the Inbox folder when you exit Thunderbird. If you check "Empty Trash on Exit" it will also empty and compact the Trash folder when you exit.