I thought that they might go into the trash bin on the computer for which they were deleted at… but I may be wrong.
“You can recover public folders or items by using version 2.3 of the PFDAVAdmin tool. The PFDAVAdmin tool uses the Exadmin virtual server to recover deleted public folders. Therefore, you have a better chance of recovering public folders or items if you use the PFDAVAdmin tool instead of using other methods. The Exadmin virtual server is typically used by Exchange System Manager to administer public folders.”
The PFDAVAdmin tool also works with Exchange 2007. You did not specifiy which version of Exchange you are using. Install it on your PC, not the Exchange server.