Eu finalmente resolvi o problema.
Eu iniciei o Thunderbird a partir da linha de comando e notei que ele estava reclamando de não conseguir abrir o armazenamento de mensagens local toda vez que eu tentava excluir uma mensagem.
Para corrigir o problema, acabei de excluir os seguintes arquivos:
~/.thunderbird/[profile_folder]/Mail/Local Folders/Trash
~/.thunderbird/[profile_folder]/Mail/Local Folders/Trash.msf
Quando o Thunderbird é reiniciado, recriá-los e excluir agora funciona.