TL;DR: I removed everyone's mailbox through EMC which deleted their AD accounts. After restoring AD accounts, people who do not have Exchange mailboxes cannot receive mail from those that are on Exchange. Email sits in Undeliverable Queue with the error "The mailbox recipient does not have a mailbox database" even though Exchange shoul dbe sending these emails to a smarthost.
I am running a trial of Exchange 2010. I imported everyone on my AD into Exchange to create a mailbox. After finding out that this will interfere with my current email server (qmail). I removed the mailboxes. I made the mistake of deleting everyone out of AD. After a mad scramble to get everyone back into AD. I restored everyones account by restoring them using their tombstones, I now have a huge problem with Exchange, but I am not sure if this is AD or Exchange that is giving me the problem.
I have setup Exchange to work with my current email server (qmail) and everything works great with sharing the domain name (public email domain name). The probelm I am having is that some users cannot email each other and Exchange gives the error "The mailbox recipient does not have a mailbox database" when it should be forwarding these emails to the smarthost (qmail server) where their account does exist. This is only some users. I know somehting in Exhcnage is holding their old email address when I imported them from AD. I can tell this becuase one of the users is changeing their emaill address with Exchange (set the new address as their reply to). Whenever someone on Exchange tries to email this user, it automaticly switches the old email address to the new one and then it is stuck in undeleviable queue. The new email account does not exist on qmial but, the old one does. Noehter of the email addresses are setup in Exchange.
This problem does not affect all users, but the users' emaill address it does affect is static and no one on Exchange can email them. Other users that are on Exchange and users on the Qmail server can email each other with no problems.