The priv.edb contains all your mailboxes. If it is intact, you may be able to work from it. You need to find out the state of the database. To do this, run the following command:
eseutil /mh priv.edb|more
When this executes, it will display header information about the database. Look down the left-hand column for an entry titled 'State'. To the right of that it will either say consistent or inconsistent. If it's inconsistent, you will have to perform a hard repair on the database - unless you have a recent backup, in which case you should restore from that and not look back. All you will have lost is messages that have been received since the backup.
If you don't have a backup, I would strongly recommend calling Microsoft and paying the $250 to have them help you get back up. I could detail steps you could take to repair your system, but when disaster strike, things can get ugly fast. Before doing anything else, copy the priv.edb that you have to another location. That way, if you perform a hard repair and it goes south on you, you can get back to the same starting point.
If anyone else should want to offer you assitance, it will be useful for them to know what state the Exchange server is currently in (i.e. have you rebuilt the server, or did just a data disk crash). It will also be useful to know if you have a good dir.edb - the edb cannot generally be repaired. The more detail you can provide the better. It will also be helpful to know what your experience level is.
Good luck,
Bob