Mailbox Reconnection

I had one of my admins thinking he was doing me a favor by cleaning up the AD Users and deleted a user he had never heard of. He also makred the users Exchange mailbox for deletion. I have recreated the user in AD and want to reconnect to her old mailbox. Is there an easy way to do this with Exchange 2003?