This line at least does seem to imply that it came from their netblock (the public google.com IP addresses also begin with 216.239):
Received: from 216-239-45-4.google.com (216-239-45-4.google.com [18.104.22.168]) by fuchsia.puzzling.org (Postfix) with ESMTP id 4D2DF1016C for <email@example.com>; Tue, 1 Mar 2005 05:58:08 +1100 (EST)
That’s kind of … uncool. One might almost say… unsolicited commercial email.
I did get something like this once before and forwarded it to firstname.lastname@example.org, only to get an instantaneous automated reply telling me that any spam I was reporting could not possibly have come from them.
Perhaps it didn’t and it’s a rather more competent header forgery than most spam. The forensics will be interesting in that case.