We recently replaced one of our elderly domain controllers, a 2003 R2 to a Server 2012, as a start in the process of upgrading all our domain controllers to Server 2012.
We currently have 3 domain controllers with following OS.
Server 2003 R2
Server 2008 R2 (PDC)
Removing the 2003 and joining the 2012 by standard procedure, and it went without a hiccup.
The following night we rebooted all the domain controllers, and we discovered that public folders could no longer receive mail.
We got the following error while attempting to send mail to a mail enabled public folder:
#554 5.2.0 STOREDRV.Deliver.Exception:ObjectNotFoundException; Failed to process message due to a permanent exception with message The Active Directory user wasn't found. ObjectNotFoundException: The Active Directory user wasn't found. ##
As a solution we rebooted the new 2012 DC and it began working again, a temporary solution.
Able to recreate the issue by rebooting the domain controllers, it happens every second time after a reboot.