Microsoft Exchange – 420 4.2.0 Recipient deferred because there is no Mdb

Last few weeks I'm responsible for migrating users from Office 365 to Office 365. Part of this migration process is to set up new Exchange 2016 server that will work as relay instead of using IIS server. No users are supposed to be created on Exchange On-Premises. I've setup hybrid, added Accepted Domains, prepared Connectors, set Accepted Domains to Internal Relay, but there's one thing missing. Any time an email is sent via relay to a user that exists on Office 365 and at the same time exists in Active Directory email never gets there. Following error message is shown

Delivery has failed to these recipients or groups:
test.user@domain.com (test.user@domain.com)

There's a problem with the recipient's mailbox. Please try resending the message. If the problem continues, please contact your email admin.

 

Diagnostic information for administrators:
Generating server: PLSERVER.domain.local
Total retry attempts: 3
test.user@domain.com
Remote Server returned ‘420 4.2.0 Recipient deferred because there is no Mdb'
Original message headers:
Received: from PLSERVER.domain.local (10.0.0.5) by
PLSERVER.domain.local (10.0.0.5) with Microsoft SMTP Server
(version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id
15.1.1531.3; Wed, 14 Nov 2018 15:26:21 +0100
Received: from PLSERVER.domain.local ([::1]) by
PLSERVER.domain.local ([::1]) with mapi id 15.01.1531.003; Wed, 14 Nov
2018 15:26:21 +0100
Content-Type: application/ms-tnef; name=”winmail.dat”
Content-Transfer-Encoding: binary

However, it works just fine when the user is created only in Office 365 as strictly cloud user. That means connectors are set up and working correctly.  So what is wrong? Why does it work for one user and not the other?