Hi, @Alex Rabbi
Based on your description, the issue may be due to "Send As" permission.
As you said, if the other user has the send as permission of user B, then the other person can send an email to user A with the email address of user B and will not see the message in the sent folder of user B, and at the same time, user B will send an email to user A as expected in the message trace. The above is expected behaviour. More information can be found Manage permissions for recipients in Exchange Online | Microsoft Learn
Then you can verify it in two ways:
1.In the Exchange admin centre, select the email address of user B to check whether there are other users with send as permissions. Click "Edit" to delete unwanted users.
2.Use PowerShell to query. You can use the following command to perform the query:
Get-RecipientPermission -Identity userB@domain.com | Where-Object { $_.AccessRights -contains "SendAs" }
You can use the following command to remove unwanted users:
Remove-RecipientPermission -Identity user1@example.com -Trustee user2@example.com -AccessRights SendAs
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".