Outgoing emails from your mail server are rejected by Postini with the error:
554 No relaying allowed - psmtp
You are routing outgoing mail through Postini. Since Postini does not handle mail for those domains, the traffic is bouncing:
1) Check the DNS MX entries for the mail server in question (e.g. for mail server mail.domain.com). From a UNIX prompt type:
dig mail.domain.com mx
mail.domain.com. 1H IN CNAME domain.com.
domain.com. 1H IN MX 100 domain.com.sNa1.psmtp.com.
domain.com. 1H IN MX 200 domain.com.sNa2.psmtp.com.
domain.com. 1H IN MX 300 domain.com.sNb1.psmtp.com.
domain.com. 1H IN MX 400 domain.com.sNb2.psmtp.com.
domain.com. 1H IN MX 500 mail.domain.com.
[In this case there is an CNAME entry for mail.domain.com pointing back to the domain which has DNS MX records routing to Postini.]
2) Remove the CNAME and create an A record for the mail host.