We recently came across an issue where we were unable to restore a deleted Public Folder. We attempted this using ExFolders, MFCMapi and Outlook and received the following errors:

Exfolders:

MFCMapi:

Outlook:

Solution:

Installing Service Pack 2 for Exchange 2010 allowed us to complete the restore with MFCMapi.