Well, I don't get it either...

Is the per account "remove deleted" setting enabled? Long press the account -> options and folders -> account options -> enable "remove deleted".
This means "remove from the app those messages that have been deleted from the server".
I also recommend double checking Thunderbird's EXPUNGE setting (as discussed above).
Finally, all else failing, long press the account and run a test (last item: "Diag: message dates", be sure to pick the right folder). At the end, you'll be prompted to email me a log file.