Have you consulted the MTA logs?
You are probably sending invalid mail or forging mail, which the likes of gmail and hotmail is refusing. Alternatively, the domain you're claiming your messages are from, may have a SPF record which conflicts with what you're doing.
Mark