We had a digruntled ex-employee make a request to our dedicated server provider (GoDaddy) to reprovision our system and reinstall the OS (Fedora 7). The OS has been reinstalled but we have not touched it since then. We want to see if we can recover our postgresql database. There is a big catch though. GoDaddy will not send us the hard drive. What they will do is take out the hard drive, attach it to a USB enclosure, and let us access it via USB from another machine. So then we could run recovery tools.
Does this have any chance of working? What do I need to consider? Please help.

Sure, it has a chance of working. Probably a pretty small one though. I'd probably just restore from backup and accept that a few transactions are lost. In any case, I hope the server has been shut down since you've become aware of this.

The larger the database is, the less likely you are to get anything useful. (Higher chance of fragmentation, overwriting, etc.)

Testdisk and Photorec are great tools for data recovery.