FYI- Answer 2 is on the correct track. Almost The only way to recover a mailbox is to restore it to a recovery server from a backup. This is tricky though because the recovery server has to be the same name as the original one.
I say almost because this is great time to mention that not only should you back up your exchange server using NTbackup locally.
You should get a 3rd party solution to Backup(COPY) all mailboxes and mail. Veritas' Backup Exec with Exchange Option is great for this function. Although it is pricey.
Word of warning, DO NOT do a normal backup! Use the copy function. This is true of any method you choose. A normal/incremental/differential destroys the checkpoint that exchange needs (this is the same for sql server).
I do 2 backups- 1 backup locally daily at the server level thru NTBackup. And 1 daily full copy thru Backup Exec. Backup exec allows me to restore ind mailboxes and mail.
NTBackup allows me to quickly restore the entire mailserver.
No points needed... I have enough.... this is just some info for you.