If you get the following while sending to an internal recipient, chances are you haven’t set your environment to accept for the domain you are sending to.
Your message did not reach some or all of the intended recipients.
Subject: Subjects are fun!
Sent: 1/1/2009 1:00 PM
The following recipient(s) could not be reached:
Lastname, Firstname on 1/1/2009 1:00 PM
You do not have permission to send to this recipient. For assistance, contact your system administrator.
user@domain.com
The example that prompted me to post this was one where admins were adding SMTP addresses on to their users for domains that they weren’t configured to be responsible for. How do we solve this? In this case the servers were Exchange 2003, so we will start there. We need to open ESM, navigate to Recipients -> Recipient Policies
Right click and choose New -> Choose E-Mail Addresses
Navigate to the E-Mail Addresses (Policy) tab, click New, and choose SMTP Address.
Enter an example SMTP address with domain you'd like to be able to send to.
Enter a name and select who you'd like to automatically receive this policy (I left mine blank as they wanted to sporadically assign the e-mail address as needed.)
Click OK. it should ask you to run this policy now, but if it doesn't you may right click your new policy and choose 'Apply this policy now...'
In Exchange 2007 you need only make your Exchange organization authoritative for the domain in question. The place to do this is under Organization Configuration -> Hub Transport -> Accepted Domains tab.
Add your domain here as authoritative and it will accomplish the same feat.
There are other causes for this issue, but this is the most common from what I have seen.