Some times when the routing tables not updated on the on premise server in a SCN hybrid setup then routing from on premise server to cloud users fails and it reports a delivery failure.
To avoid this SCN service should send some administration command to directory sync server and then that request to update the routing table should be sent to all on-premise mail servers to avoid any potential mail routing issue.
Current workaround it to issue the below commands on all on premise mail servers.
Show nlcache reset
Tell route update config
It is also recommended to run the command load updall -t ($Groups) names.nsf -R on the administration server.