I have encountered this problem on my own personal mail server only once a while. It’s ratehr rare, and happends only when sending mail to some specific domains.
My first notion was based on the claim that if it works for anywhere except for these one or two domains, the problem is with these one or two.
My second notion was to investigate it somewhat further, to be able to assist the owner of the domains in question in solving their problem, or supply them with links showing possible solutions.
I was very surprised to discover that the problem was here. It was a bug with spamass-milter, used by my server to connect ol’ Sendmail and Spamassassin together, and it appeared only in version 0.3.0.
I’ve just upgraded to version 0.3.1, and it works correctly for these domains.