When Gmail Messages deleted in Apple Mail keep coming back

Apple Mail account settings for Gmail, with the mapping of the Trash Mailbox to Gmail's Gmail/Bin folder highlighted

For the last coupe of weeks I had this weird behavior that whenever I deleted a message from my Google Workspace inbox through Apple Mail on Mac, these messages never disappeared from the web interface. And after fetching new messages, they also crept back into Apple Mail.

Looking into the account settings, I saw that the Trash Mailbox had somehow been set to None. After changing it back to [Gmail]/Bin, deleting messages  worked again as expected. Also, I had to change it back twice until the setting sticked (hopefully 🤞).