Do other users in your organization have the same issue?
Where did you delete emails? Outlook desktop, OWA or other clients?
Are these deleted emails still in the mailbox folders if you access OWA? Do you see these emails if you run the following command in Exchange Online PowerShell?
Search-Mailbox -Identity <Mailbox Identity> -SearchQuery 'Subject:"<Subject>" AND From:"<Sender>" AND To:"<Recipient>"' -EstimateResultOnly
Search-Mailbox -Identity <Mailbox Identity> -SearchQuery 'Subject:"<Subject>" AND From:"<Sender>" AND To:"<Recipient>"' -TargetMailbox <Mailbox to receive the search report> -TargetFolder Test
The first command will estimate the search result, the second one will create a target folder in the target mailbox and send a search report to this folder(The report includes the searched emails.).
More details about the search cmdlet: Search-Mailbox
If you didn't see these deleted emails on other clients after being deleted, I think it may be a sync issue(Perhaps some network issues), try to manually update folders or recreate profiles and see if there is any difference.
Besides, you can also try running the following commands to delete emails(Please note: To avoid losing important emails, you need make sure the search query condition is accurate and use the second command to check if emails are the ones you want to delete.):
Search-Mailbox -Identity <Mailbox Identity> -SearchQuery 'Subject:"<Subject>" AND From:"<Sender>" AND To:"<Recipient>"' -DeleteContent