Hi @Bob Pants ,
Thank you for posting to Microsoft Community. We are happy to help you.
Based on your description, I understand the issue is the mails from new mailbox created in EXO would ends up in the junk folder and you may want to seek some suggestions.
May I know this issue happen with only Outlook mail system? If so, it could be related to the email system provider since only Outlook identify all emails from your organization as spam.
As the question why the accounts are created in on-prem AD works fine, you should notice the email headers for cloud-created mailboxes might differ slightly from those created through "Enable-RemoteMailbox" command. Please compare the headers from emails sent from cloud-created mailboxes against those from on-prem AD-created mailboxes.
If there are anything else I can do for you, please let me know.