Recover back-up data

I need to recover our Exchange public store so I can retrieve so contact info that a department lost. We had to rebuild our Exchange databases and the person that extracted the public folder info did not verify that he got all the information. Now I have to try and recover it. We use Vertas for our back ups and our Exchange server is the only server with a tape drive. What sugestions do you have to recover this info?

I was thinking about installing Exchange on another server and recovering my backup to that server. Then extract and verify the information.
What thoughts or tips do you have.

I have put a higher number of points on this so I can accept multiple answers