Never come accross this problem, but hit lots of others when first started using Cache Mode. This is now disabled except for users who really do need it (Very few).
Suspect your problem is due to running in Cached mode.
You say you have checked settings on Primary Mailbox ? on Server only, or actually on PC with this Mailbox open ?
? Do users usually leave PC running with Mailbox Open ?
Could be localy cached setting that only gets cleared when Mailbox is closed, and re-opened.
( The GAL (Global Address List) is downloaded to be accessible during the cached mode function. This list contacts the email address that is causing the “NDR”. To force this to update, turn off cached mode and close Outlook. When Outlook is reopended, turn Cached Mode on, and it will force the Cached version of the GAL to update.