Question: Has this been occurring for awhile? I've seen this happen with a new Exchange system after migration from Groupwise. Generally, this error is caused by an invalid recipient address.
For example, using the Personal Address Book (PAB)to address mail. Typically, when migrating to Microsoft Exchange, users will tend to use a PAB entry to address mail. In some instances, the address looks like the friendly name that is also in the GAL, but when getting details of the user in the PAB, the address will contain that of the old mail system.
Have your users imported Address books?
Have you moved any Exchange servers from other sites? or imported distribution lists lately?
One other cause that I have seen is the addressee's mail server is unavailable to accept the message as it is being distributed. If the mail server at the receiving end has issues, it may refuse to accept mail. Usually internet mail is retried for 72 hours, but sometimes its returned quickly.
If this was happening to everyone, I'd suspect either your DNS information or Gateway on your mail server is incorrect or the MX record on the DNS server at your ISP is incorrect...but if two records exist for you, it could work sometimes and not others.