Since there is no backup the messages are gone. To get the user accounts setup again, you should be able to recreate the accounts on the Exchange server, if the alias matches then when you rerun the configuration wizard on Unity, it should plow through Exchange and link up the subscribers to the mailboxes. I have seen this happen where duplicate accounts have been created, because something does not match exactly. In that case what you can do is use the migrate subscriber data tool (found in tools depot) and move the subscriber information (password, settings, etc) from the old account to the account that you created on Exchange. See if this gets you close.
Steve
