As noted in the post title, after enabling Out of Office (Automatic) replies, the replies were not being sent out
We found in this case that our issue with the Out Of Office (OOF/Out Of Facitility) not working was due to all of the mailboxes in question having the ForwardingSmtpAddress value set, which is the "Forward my e-mail to" option in the Connected Accounts area in the OWA options/control panel.
We ran the PowerShell command below to clear this value from all of the affected mailboxes:
Get-Mailbox | Set-Mailbox -ForwardingSmtpAddress $null
Once we cleared this value, the OOF began working.
As a workaround for the forwarding, there are a few options:
1) Create a Transport Rule (in the Mail Control, Rules section of the Exchange Control Panel) and using the Advanced Options, choose to BCC the messages to another recipient.
2) Use the PowerShell command and set the -ForwardingAddress instead of the -ForwardingSmtpAddress
Set-Mailbox username -ForwardingAddress firstname.lastname@example.org
3) An Inbox rule can be created to do the forward or redirect:
#1 and #2 will be invisible to the mailbox owner/user
#2 actually works a little differently than when ForwardingSmtpAddress is set, and does not break the other auto-replies.
After checking these, we found that the OOF still would not work for an admin mailbox that was affected. We found that this was because the admin mailbox is specified as the NDR recipient in the Journaling settings for the organization, which also stops auto-replies and auto-forwards from working, as noted in https://support.microsoft.com/en-us/help/2829319/transport-and-mailbox-rules-in-exchange-online-or-in-on-premises-excha