Ran in to an interesting issue/bug when retiring my last Exchange 2003 box. Followed all the steps and everything went normal in retiring the last server. Then proceeded to reboot one of my Exchange 2010 servers and started to see a few of these errors in the app log:
The store driver couldn't deliver the public folder replication message "Folder Content (firstname.lastname@example.org)" because the following error occurred: The Active Directory user wasn't found..
Found a similar issue on the Windows Server Essentials and Small business technet blog although the error was slightly different:
In any case, removing the empty server folder resolved my specific error as well. Just throwing that out there in case somebody else sees the issue.