Imagine for the moment that the OP's IP address has changed during this time and they don't have SPF or DKIM configured. Or imagine SPF is misconfigured to say

Imagine for the moment that the OP's IP address has changed during this time and they don't have SPF or DKIM configured. Or imagine SPF is misconfigured to say "only IP 1.2.3.4 is qualified to send email for this domain" but they've since moved to another IP. Or imagine their DKIM configuration is broken and their messages aren't validating. There are a ton of ways you can configure a mall server so that recipients can't reliably tell you're not sending spam: it's not just what content you send but also the reputation of your IP and the signals you choose to send via SPF and DKIM. This isn't specific to Google: all the companies that receive email have the same difficult problem. Email is the only major fully open federated push protocol, and spam has come close to killing it. (Disclosure: I work for Google, nothing related to mail, speaking only for myself.)