According to your information above, the user is deleted before you configure Exchange hybrid and sync to cloud. And DBEB not working for this account.
DBEB block all messages sent to email addresses that aren’t present in Azure Active Directory.
Try using the commands below to see any result returned back about the user:
Get-AzureADUser -ObjectId "testUpn@tenant.com"
Get-Recipient -Identity <MailUserIdentity> | Format-List
Detailed information Manage mail users in standalone EOP
In addition, have you checked in onprem AD that the deleted user is not able to be found?
Could you please provide the complete NDR you received for that account?
Some further information about DBEB attached here as well: In Deployment: Directory Based Edge Blocking for Exchange Online Protection
If an Answer 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.