From the Sysadmin of the box:
"Resolved, in theory - we were being hit by a bug in SpamAssassin 3.1.0."
I am not sure what exactly about Gmail made SpamAssassin go nuts... but it is resolved for now.
Thanks to everyone who assisted, including Google, who were pretty quick to at least acknowledge my report.
Now, if only their details were on puck.nether.net