Just looping the list in on the status:
We're talking with a support person from Google, they've made a couple of suggestions that I've forwarded to Ops (specifically SPF and DKIM).
They also asked for the headers of some of the messages, which you saw I related to the bug. I sent them the one Alex shared.
I'll let the list know when I have a more solid answer (ie: "we're all fixed" or "email hates us").
Greg