We are not having any trouble sending to any other domains, nor are we having trouble receiving messages from people outside of our Exchange Server domain. Any suggestions?
There are many things that could be happening here. You didn't state whether only this particular user can't send to the address, or whether the same problem applies to anyone else in your company.
That said, I'd start out by looking at the specific SMTP error message in the non-delivery report (NDR). If that doesn't help, run an nslookup command and find out what MX record is associated with the domain that's giving you problems.
Then, telnet to port 25 of that server and try sending a message manually to see whether (i) the server is indeed listening on port 25 as expected, and (ii) the server accepts the message or gives a detailed error message.
Also, have a look at one of my previous posts, "Error: 'You do not have permission to send to this recipient" for further assistance.
One other possible solution is to check and see if your email header has a reverse DNS lookup. If your IP is dynamic or your ISP has not added a valid reverse DNS lookup address (i.e., one that is not on any blacklists), you will get results something like what you are describing.
As David stated, there is not enough information to do anything but second guess.
Do you have comments on this Ask the Expert Q&A? Let us know.
Related information from SearchExchange.com:
This was first published in April 2007