Don't I know it. This happened to us but not with Google. We use Exchange Online (Office365) and have DKIM, SPF headers configured. At some point our emails stopped being received by bell and cox emails addresses ... sporadically but sometimes for days at a time. It turned out that the spam filter provider (used by bell and maybe cox) correlated one innocuous phrase in our confidentiality notice (which is appended to all outgoing email signatures) with spam and therefore marked the entire email as spam as well.