What is the setting for deleted messages in Server Settings in Account Settings? Is it 'Just mark it as deleted', which is recommended for gmail accounts? Is the target for deletions a subscribed folder? Mail services use different names, e.g. Trash, Deleted, Deleted Items etc.

That worked. "Move it to this folder" was selected, but it didn't actually show a folder in the selection box. Weird. Kinda makes me wonder where all the messages went that I was deleting. Thank you very much! I hope you enjoy your day.

When messages are deleted, they are copied to Trash, but are just marked as deleted in the original folder. They aren't actually irreversibly removed from the computer until the original folder is compacted - which means they can be undeleted before compacting is performed.

In your case, where deletions 'had nowhere to go', they were probably just marked as deleted in the original folder.