Messages being bounced (postfix & gmail mail servers)

Sometimes.

It's very confusing. We have a service and you get a confirmation e-mail with a link to confirm your account, etc.

If a user is sending an e-mail from one of their own domains; like [email protected] or [email protected] or [email protected] then it always reports that it can't find them, or the user doesn't exist.

Now, all this is is a php mail function (from what I understand) and it's sent from our web servers. These web servers are a part of our domain, and we use Google, and have the appropriate SFP & MX entries.

The most common message that I get is a claim that the address does not exist or that it's mistyped, but -- in all of the cases, the e-mail exists & has no extra .'s or spaces, or letters.

The email account that you tried to reach does not exist. Please try 550-5.1.1 double-checking the recipient's email address for typos or 550-5.1.1 unnecessary spaces. Learn more at 550 5.1.1 http://support.google.com/mail/bin/answer.py?answer=6596 el5si16864532vdb.30 - gsmtp (in reply to RCPT TO command))

I've tested this with one of my @gmail.com accounts and have not had an issue with it sending me an e-mail.

So, since it tends to have a higher reject rate of these @randomtheirdomain.net here, could it be us or them? Or both?

Edit; I'd like to note that when I set up postfix, I set it up using the postfix's "null client" settings (http://www.postfix.org/STANDARD_CONFIGURATION_README.html#null_client)

I did this because I figured the server would only ever be sending mail, and should not receive and/or do local mail delivery.