We're using Exchange Server 2003 running on Windows Server 2003. The mail server has worked perfectly for over a year. We recently added a new batch of users to the AD. When sending mail to these new users, we receive an NDR (Exchange error #5.1.1).
The e-mail account does not exist at the organization this message was sent to. Check the e-mail address, or contact the recipient directly to find out the correct address.
Email sent between the older users still works fine.
The weirdest part of the problem is that when I send two emails to a user in succession, the first will bounce and return an NDR and the second will go through just fine.
We've tried removing users and readding them to the domain and updating and rebuilding the Recipient Update Services.