Mail enabled Public Folder Recipient not found
Edit 6th may 2010: Similar issue with same solution is confirmed and will be patched by Microsoft. See here.
Recently I transitioned an Exchange 2003 Server to Exchange 2010. For the client redirection, I mostly wait two week before decommissioning the old Exchange server. Mailboxes, mail flow, remote access and the default Public Folder are all transitioned to the new server. So, in the event of a failure of the old server, the organization would not notice it.
Eventually most or all clients have been redirected, the new server has proven its stability and nothing stands in the way of decommissioning that old server.
Symptoms
So, the decommissioning in this case was troublesome. The setup exited halfway with an error and after that the setup could not remove all of Exchange, because it could not find the items to remove. Even the setup.log couldn't help me any further. Eventually I decided to manually remove Exchange 2003. The server itself would also be decommissioned; any leftovers on the server would be resolved eventually.
The new environment worked without any problems after that. But around 24 hours later, the administrators noticed that the mail enabled Public Folders couldn't receive any mail and the sender would get the following NDR:
554 5.6.0 STOREDRV.Deliver.Exception:ObjectNotFoundException;
Failed to process message due to a permanent exception with message The Active Directory user wasn't found.
Every mail enabled Public Folder was affected, even new mail enabled folders after this issue first arose. The folders where present in the "Public Folder" Address list, GAL and so forth. Even after re-generating the Offline Address book, the issue persisted. I have tested this via Outlook 2003/2007 and 2010 (beta) and via Outlook Web App. No mailbox enabled user had this issue and as far as we know no mail user had related issues with receiving (SMTP) mail.
I'm not sure of the exact steps, but when I tried to make a recipient with the same SMTP address as the troubled Public Folder, Exchange would give the same mail address. In other words, Exchange knew of the existence of that recipient, but couldn't find it.
A search on the internet wasn't successful in finding a relevant knowledge base article or such, although others seem to have the same issue or related issues. The pattern I noticed was that recently an Exchange (2003) server was decommissioned. See here and here. This post describes the same issue, but only has a work intensive workaround
Both first posts are related to Public Folder replication, but as this replication uses SMTP this issue could have the same cause.
Solution
As stated in the comments in both first posts, the resolution was to remove the (empty) Server container via ADSIedit. In my case it was the server container of the administrative group recently containing the Exchange 2003 server. In my case the location was:
CN=Servers,CN=First Administrative Group,CN=Administrative Groups,CN=First Organization,CN=Microsoft Exchange,CN=Services,CN=Configuration,
DC=domain,DC=local
I assume that the failed setup may have had a role in this, although I still find it curious that an empty container could have such a detriment effect on mail enabled Public Folders.
Possibly clues to the underlying reasons can be found in the 24 hour frame and actions taken by the setup of perhaps Exchange 2003 or specific behavior of Exchange 2010 regarding recipients. I have never experienced this issue with Exchange 2007.
Conclusion
Check the above mentioned container with ADSIedit after you decommissioned your last Exchange 2000/2003 server. Remove the empty Server container (at you own risk and be sure to have a backup !!).
Further Reading
Public Folder Mayhem on Exchange 2010
Public folders not replicating betwen exchange 2007 and 2010