Check the SMTP mail server logs, as a start. Look for the connection requests for the delayed messages, and also particularly look for 450 try-again-later responses from your mail server.
If you're seeing 450 errors in the logs, you're probably getting delayed by greylisting, as the OS X Server box learns about the various Google mail servers. Greylisting will generate that response for the first few contacts with a "new" mail server, as that greatly reduces the volume of spam. The spam engines don't retry their messages. Real mail servers do.
Here are some details on disabling greylisting, though I generally don't recommend doing that.
So I sent myself a test email, from my gmail account, to my main account. The email hasn't arrived, and this is what showed up in the error log (with logging set to "information"):
Jun 11 13:47:08 macfixer postfix/smtpd: connect from mail-qc0-f174.google.com[220.127.116.11]
Jun 11 13:47:09 macfixer postfix/smtpd: NOQUEUE: reject: RCPT from mail-qc0-f174.google.com[18.104.22.168]: 450 4.7.1 <firstname.lastname@example.org>: Recipient address rejected: Service is unavailable; from=<email@example.com> to=<firstname.lastname@example.org> proto=ESMTP helo=<mail-qc0-f174.google.com>
Jun 11 13:47:09 macfixer postfix/smtpd: disconnect from mail-qc0-f174.google.com[22.214.171.124]
If it's greylisting like you say, why is it being such a problem all of the sudden, and why only for gmail?
So disabling graylisting worked, email is now instant. But now I do get WAY more spam. Mostly "online pharmacy" spam, the shittiest kind. So is there some kind of middle ground. Like using greylisting but ONLY on hosts that do not come from a valid source, as dictated by the SPF record? That should give me the best of both worlds?