http://en.wikipedia.org/wiki/Greylist

Unrelated to your problems with gmail.

extra update: we are using Google Apps and have their mail servers set up like documented in their documentation.

Those are the only MX records. Might that be an issue?

I don't believe so.

Mine are all google's too and it's fine

EXTRA UPDATE:

how can we make sure that google doesn't see us as spam. I've read that gmail will get an email from @ourdomain.com and it will run an nslookup or something to see if we actually have a receiving MX server set up?

Can someone confirm this and give me the nslookup command that I can test with. I'm confused as nslookup on ourdomain.com gives the correct MX records, but mxrecord on WWW.ourdomain.com doesnt.

The hostname of the machine we are sending with is www.ourdomain.com

Is that something to be worried about?

Here are three things that help:

1) You need to have a proper MX record setup, as you've noted
2) Your IP's reverse DNS that you're sending from should be the same as the domain you're sending mail for (as in, foo.com -> 1.2.3.4, and 1.2.3.4 -> foo.com)
3) You should set up your SPF records properly.

Thank you for helping out. Can you let me know how to correctly check these 3 factors?

1) I have MX records set up for google apps, just like they state in their documentation. I don't have an MX record for my own machine since I don't receive email on that IP. I do have an SPF record that mentions the google apps MX servers as valid senders

2) My email headers now say:
Received: from mail.ourdomain.com (www.ourdomain.com [x.x.x.X])

should I test RDNS for mail.ourdomain.com (this is the hostname) or for www.ourdomain.com ? How do I test this 100% correctly?

3) The SPF say "pass" in gmail email headers, is that OK?
Because the test on http://www.openspf.org/Why gives me the following:

The SPF check gives me this: An SPF-enabled mail server rejected a message that claimed an envelope sender address of support@ourdomain.com. An SPF-enabled mail server received a message from ourdomain.com (x.x.x.X) that claimed an envelope sender address of support@ourdomain.com. The domain ourdomain.com has authorized ourdomain.com (x.x.x.x) to send mail on its behalf, so the message should have been accepted. It is impossible for us to say why it was rejected

You don't need an MX for the hostname of the server, only for the domain of the email sender.

Reverse DNS only needs to match the hostname of the mailserver, not the domain you are sending from. There is no requirement that the domains of the server and the email sender must match.

If you really want help, you'll need to tell us your real domain. By providing imaginary details, you are just getting guesses as to what your problems may or may not be.

In my experience no matter how well you set up all these details, it is likely that some of the major providers will see any new mailserver as a spam source. Once you have been in operation for a while and enough users have clicked "Not Spam" or whatever, then maybe you will build up enough reputation to go straight into inboxes.

Your mailserver is announcing itself (HELO) as mail.ourdomain.com, but RDNS says that your IP belongs to www.ourdomain.com. It really doesn't matter which name you use, but ideally you would have one consistent hostname for your mailserver.

Forward DNS: mail.example.com -> 1.2.3.4
Reverse DNS: 1.2.3.4 -> mail.example.com
HELO: mail.example.com

In postfix, you can set the HELO name by smtp_helo_name, (or better yet just properly set myhostname) in main.cf.