If you deleted the account in AD the user profile will still be on the
client machine under Documents and Settings. You will have to recreate the
user and give thems rights to the mailbox. There is no way to undelete the
account. All of the users data will still be preserved on the client within
their profile.
Just to add on to that. If you are using Exchange, which
are you using? I am only vaguely familiar with Exchange
2000. So when you create the user in AD I don't think you
are supposed to create a mailbox for the user. Once the
user is created, open the ESM, right click on the user
just created and select reconnect. Once the user logs on,
they should be able to open their mail.