If you have hybrid exchange and if you have 365 cloud only user (not sync from onprem), email send from on-premises users will fail because your exchange is authoritative for your domain and will not route to external exchange to deliver your organisation email. The fix is simple,

1. Create a contact with the 365 email address on your on premises exchange, so the email will be routed out to 365.

2. Alternatively, you may delete the cloud only mailbox, synch the new user from on-premises AD (via Azure AD connect) assign Exchange license to the user to create 365 mailbox, and restore your deleted mailbox if needed. Now, on-premises users will be able to send email to the new 365 synchronised user.