My guess is gmail is moving them back as they still exist in other folders. the "all mail" folder is gmail's archive, so if mail is in other folders it must also be in all mail.

Matt said

My guess is gmail is moving them back as they still exist in other folders. the "all mail" folder is gmail's archive, so if mail is in other folders it must also be in all mail.

That may be it. Nevertheless this seems obscure...

I removed the messages from Inbox and Sent Mail, as well as from All Mail, and they seem to not reappear.

However, they are still listed in Gmail's web interface under All Mail, why?

Gmails mail system has no folders, it only has labels. If a mail has an inbox label it appears in the inbox. If it has a trash label it appears in the trash. If it has important, inbox and family then it appears in all three. The real home of these emails is the all mail folder however, that is googles canonical location from which all mail is derived.

So what you see in Gmail folders is an illusion and what you see in Thunderbird is even more of an illusion. Google call their IMAP implementation GIMAP, that is because they have developed a hybrid process to make their ideas on mail and storage look like IMAP to mail clients. Due to the weirdness of GIMAP, Thunderbird ignores a lot of settings that would be available to other IMAP mail accounts, simply because trying to provide them would leave the gmail account scrambled, or at least significantly messed up. Things like specifying an Archive folder among many others are simply not available to gmail accounts.