Hi Adam,
wow i dont want to be in your shoes and i hope is not a production box.
I will do what i can to help you,
Lets start with the basics, Did you delete ALL users in AD?
Under which account were you log on when you deleted the users. It is not clear to me how the system would allow you to delete the current user.
Do you have a back up of the mail boxes? was there any mail in it?.
You do not seem very concern about their mail.
WilsonJ