To fix the problem, I opened IIS on the Exchange server and checked the following directories under the default website (the root site(default web site), oab, autodiscover).
This group was used to enable mail flow between the legacy servers & Exchange 07/10.
Upon inspection, this customer’s Exchange 2013 servers had been made members of this group.
By default, there is a Deny entry (seen below) for the “Accept Organization Headers” permission.
In our case, we unchecked Deny for this permission & after restarting the MSExchange Transport service the issue went away; we then started receiving OOF messages as expected.
If Mailbox-A turned off their OOF then the message in the queue would eventually be removed without an NDR.
This situation not only prevented the customer from utilizing Out Of Office as it was intended to be used, but it also caused NDRs to be generated to anyone sending them emails while OOF was enabled.
Microsoft Support explained that this permission is used when the system needs to issue the “MAIL FROM” SMTP verb; which is required when generating OOF messages or similar Rules.
I was excited to figure out the cause of the issue but was also curious why this would be affecting us since as far as I understand, only Exchange 2000/2003 servers were ever members of the Exchange Legacy Interop security group.
In fact, I found that I could recreate the issue without even enabling OOF.
If I created a mailbox rule to have the system send an email to the original sender (effectively functioning like an OOF) I would experience the same behavior.
In addition to this, if you looked in the queues you would see the original email message (not the OOF message) queued even though it had already been successfully delivered.