That does seem somewhat "strange" that it happened. Can you remove the messages in the trash?
Additionally, wonder if it was a one time "glitch" with AT&T?
Also, do you ever have deleted EMails permanently removed? I use Outlook 2016, and there is a simple procedure for doing that: when I select an EMail for deletion, it (of course) goes into the Trash folder. Then, when I right click on the Trash folder, one of the choices is "Empty Folder". Once I select that, I then get a dialogue, asking me if I want to confirm the Permanent deletion/removal of the EMails there. I select yes, and they are gone.
For Apple's Mail program, this link discusses this:
https://discussions.apple.com/thread/6143397
Permanent deletion/removal, of course, has the added benefit of saving disk space, which is always a good thing.