Delivery has failed to these recipient but the recipient has already been deleted from AD

Hi Exchange community,

I am having some issue where when a user mailbox received any email, that user will receive an email from Outlook saying undeliverable to a recipient. The thing is, that recipient has already been deleted from AD so I'm not sure why we are getting this message:

I've tried to check the following place but no joy:
1) Check mailbox delegation for the recipient name but the name of the recipient does not exist in the mailbox delegation list

2) Check security settings in the AD of the affected mailbox but the name of the recipient has already been removed from the security settings

3) I've tried updating all users and default global address list address book but still receive the same undeliverable message from Outlook.

4) No forwarding rule to the recipient has been configured for this mailbox

Really appreciates if anyone has some insight in this. Thank you in advance!