Easiest approach is to recover through the Outlook Web Access. You can access the public information store through your web browser. Just point it to:

http://servername.domain.com/public/?cmd=showdeleted

(where servername.domain.com should be replaced with the FQDN of your Microsoft Exchange Server - the FQDN stands for the fully qualified domain name)

You should now see the deleted folder in the list. Highlight it and click on "Recover". That's it... or not?

Well, if the folder structure is too large, then you may need to do some additional work. You'll know if the folder does not reappear and if you see strange event log messages on your Exchange Server indicating that the version store size limit has been exceeded (Event ID 623).

That means you'll have to increase that before your recovery will be successful. Simply follow the directions from Microsoft on this page: http://support.microsoft.com/kb/922501/en-us

Also, make sure the user account you are using for recovery has the rights to create toplevel public folders (if you are trying to recover a toplevel public folder, recovery=create).