I wrote a script a while ago that can remove invalid delegates from a mailbox using a mixture of EWS and Exchange PowerShell. The limitation of the original script is that is didn't do anything about the hidden rules that forward messages to delegates, which means that the unexpected NDR issue (as described here) would remain.
I've revisited this script recently, and have been able to add support for this hidden message. More accurately, the clean process deletes this hidden message (which contains all the forward rules), and when the valid delegates are written back to the mailbox, this message is recreated (correctly, without the invalid rules).
The script requires EWS only (it no longer requires an Exchange PowerShell session). For this, you will need to install the EWS Managed API (any version should work, though the latest is always recommended).
Reset-Delegates -Mailbox <string>
[-Username <string> -Password <string> [-Domain <string>]]
-Mailbox Mailbox SMTP email address (OR filename for source list of mailboxes; text file, one mailbox per line)
-PurgeInvalidFreeBusy If specified, any invalid FreeBusy messages (those not defined in PidTagFreeBusyEntryIds) will be deleted
-Username Username for the account being used to connect to EWS (if not specified, current user is assumed)
-Password Password for the specified user (required if username specified)
-Domain If specified, used for authentication (not required even if username specified)
-Impersonate Use EWS impersonation to access mailboxes
-EwsUrl Specify the EWS URL (otherwise autodiscover is used, which is recommended)
-IgnoreSSLCertificate Ignore any SSL errors
-EWSManagedApiDLLFilePath Filename and path to the DLL for EWS Managed API (if not specified, the scripts will look for any version)
-PermissionsLogFolder Path to the folder in which reports of mailbox permissions will be created
-WhatIf If specified, no changes will be written - the permissions will be logged
.\Reset-Delegates.ps1 firstname.lastname@example.org -impersonate -whatif
.\Reset-Delegates.ps1 "email@example.com" -Username "firstname.lastname@example.org" -Password "password"