Hi Christine,
That very much cleared things up.
Are you using Gmail as an IMAP account in Outlook for Windows?
Since this only affects Gmail, this points to how Gmail sync works. Outlook follows the server, and Gmail controls the actual delete action. When you delete a message in Outlook, Gmail may move it to All Mail instead of removing it. On the next sync, the message returns to Inbox. The message “you can't permanently delete these items” also fits this behavior with IMAP accounts. I would recommend to sign in to your Gmail settings in a browser, go to Forwarding and POP/IMAP, then check what happens when a message is deleted. Set it to move to Trash or delete immediately. Also check Gmail web and confirm if the messages still exist there after deletion. Outlook will always reflect what Gmail keeps on the server, if that's the case, the fix needs to be done on the Gmail side.