Google having difficulty delivering to Gmail?

We are doing informal testing on Gmail deliverability today after a report from a client that they are getting some of our mail in their Gmail Spam account.

So far we've sent emails to about 40 different internal test Gmail accounts, a mixture of old and new, and sure enough, a percentage of emails are getting thrown into the junk folder. It seems fairly random so far, with identical emails going to both the spam and to the inbox in the same account.

So I did a few searches to see if anyone else is experiencing the same problem, and we are not alone:

Just this month, Andy Beard noticed false positives, and then while checking his spam folder found a Google email alert in the Gmail spam folder! (oh the irony)

After a bit more research I can see this this phenomena started happening after the new year, and has been continuing since:

January '08: Another Google mail in the Gmail spam folder

February '08: Gmail-false-positives-are-on-the-rise

March '08: GMail spam filter is throwing up some false positives today

April '08: Fish out the false positives

May '08: Are Gmail's Spam Filters Getting OverZealous?

The good news is that it is occasional - the bad is that it's random and so far unpredictable. We've seen message headers, content and IP addresses that are identical being both delivered and junked at the same time.

Can it be fixed? We'll see...