New users can't recieve email from outside the organisation. Exchange 2007.

We have a situation where new mail users can be created within Exchange but cannot receive messages sent to them from outside the organisation. These same addresses work fine internally and can send email to the outside without any problems.

The issue also applies to mail aliases placed on users who have working exchange accounts. Messages sent to their alias from outside the organisation bounce back

External senders receive a similar error to the one below when sending too the new users/aliases:




Running a verification test on network-tools.com produces the following:

Additional information - I personally don't know when this began or how long this may have been happening for as I've just taken over on this. I suspect it has something to do with the recipient update policy, however the account in question, I understand, has been around for two weeks already.