Do you mean that the outbound email from one of your users will show in the deleted folder of other mail server?
To narrow down this, I want to confirm with you:
- What is the mail server that you used?
- Whether other users on your mail server have this issue?
If only this user has this issue, it means this user may be blocked by the recipient mail server.
If this issue occurs on all your mailboxes. I would check with your whether this issue occurs when you send emails to other mail server?
If this issue also occurs on other mail server, please have a check with the SPF for your Mail server.
If this issue only occurs on this one recipient server, I think your domain may be blocked by their server. Try to confirm with the admin of that mail server.
If the response is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.