Recipient address rejected: User unknown in virtual mailbox table

One of our client that is having issues emailing to their domain (@client.com) from only one external domain & mail (@supplier.com) after migrated one mail host provider to Exchange Online (O365).

We can send an email to them and they get it, but they cannot respond back to the email or email us directly. I asked one of our clients to take a screenshot of the error message and this is what I get.

As per the exchange mail trace, the email didn't reach to Exchange Online (O365).

We have asked the mail host provider to check and not get it results.