Exchange Server reboot now have "You do not have permission to send to this recipient" error

My Exchange server locked yesterday after failing to find the DC which had crashed.

Now I have a problem with 3 mailboxes.
Users A & B have allowed Full Mailbox access to User C. This was done by me over a year ago and has been working fine. No "Send As" permissions were involved at any stage.

Since yesterdays reboot, whenever User A or B send an email it is not received by the recipient (not specific ones, everyone)  but User C receives a Sys Admin email in their inbox stating they do not have permission to send to the recipient(s) concerned. This email shows User C as the original sender.  I have removed the full access permissions and unattached User A&B mailboxes from User C but this does not resolve it. I have deleted User C profile and recreated without resolving. I have recreated permissions setup - still no joy.

Presumably I should just delete and recreate the mailboxes now - or is there a simpler answer?

Thanks
Michael