Once I had a similar problem and it turned out that the reason was that the Envelope-Sender did not have a domain part, so foreign mail servers did not accept the mails because they did not know the user names.
Hope this helps..