Apologise for late reply, the issue has been resolved.
Great to know that you've already resolve your issue and really appreciate it for your sharing, so that others experiencing the same thing can easily reference this!
By the way, since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others.". and according to the scenario introduced here: Answering your own questions on Microsoft Q&A, I would make a brief summary of this thread:
*
[550 5.1.10 Bounce from user whom the email was not sent to.] **
**Issue Symptom: **
It is an intermittent issue.
Some users report that they receive following Bounce message:
Generating server: Exchange Serer
userX@keyman .ac.uk
Remote Server returned '550 5.1.10 RESOLVER.ADR.RecipientNotFound; Recipient not found by SMTP address lookup'
The bounce is regarding user to whom the message was not sent to.
The user have been removed from AD few months ago.
How it is possible that when user sends email it sometimes goes to userX as well?
The Solution:
I spotted that all of the messages he was sent had a spam flag within the data when you looked on the Exchange trace. I also noticed that the messages to userX were a forward of the original message, which led me to think there must be a rule somewhere other than Exchange online (which I'd already checked). After a bit of googling I was pointed to the Security area of Azure where there are anti-spam policies. In the outbound anti spam policy I found the forward to userX.
You could click the "Accept Answer" button for this summary to close this thread, and this can make it easier for other community member's to see the useful information when reading this thread. Thanks!