I'm an IT consultant for a branch office of a company, there Email servers are out of my control, but I wanted to see if this was definately an issue that was out of my hands.
One mail account started getting these errors when sending mail to addresses generally outside of the companies domain. This account has been active for nearly 2 years, and the company has several hundred employees but I've only seen it on one account. The error is reproducable on several machines using Outlook 2000, Outlook XP, Outlook 2003, and Outlook Express 6. I haven't tried any non-Microsoft clients, but I don't think that would really help. The account is connecting through POP3 and mail sent through OWA works fine.
Does this appear to be an issue on the Exchange server or is there something else I need to check?