It sounds as if the issue is on the receiving end. If this is occurring on domains you frequently send to, try doing as this link suggest.
http://social.technet.microsoft.com/Forums/en-US/exchangesvrtransport/thread/19d5d818-71d2-4959-b7c4-27f653ffcbd8