When a new message arrives on GMail it gets immediately synced with TB. So that works fine.

When I delete a message in TB it goes to the Trash folder.
- It no longer show in the GMail inbox. Good.
- It does not show in the GMail Trash folder.

I think that last one is the source of the problem.
The current situation is that all folders on TB and GMail are in sync. Except the All Mail folder.
- On GMail it contains messages that are long ago deleted.
- In TB it looks fine.

I can't reproduce it, but at least once TB resynced All Mail and all the deleted messages were back.
To be honest I don't think it's a bug in TB, because I had the same problem with another email client.
So it may be wrong configuration of  TB and/or GMail.