When users try to recover deleted items from Outlook, they receive an error message saying that they don't have the required permissions. Why can't we make deleted-items recovery work for public folder items?

Your users probably don't have the required permissions. Remember, you must set permissions for the public folder hierarchy, not just for the individual public folders. You can take two approaches to troubleshoot this problem. First, you can give the Everyone group or the Authenticated Users group Full Control access to the hierarchy object. However, this approach might give users more access than you want them to have. As an alternative, the Microsoft article "XADM: You Cannot Recover Deleted Items from or Modify the Contents of Public Folders Through Microsoft Outlook" (http://support.microsoft.com/?kbid=811358) details the default permissions that you should apply to the hierarchy. After you review these settings, you can manually verify that they're in place, then temporarily grant Full Control access to enable the recovery. Be careful; if you configure the permissions incorrectly, clients might not be able to access any public folders.