Parece que encontrei a resposta.
O Gmail não gosta de ter duas entradas "incluir" no SPF.
Eu tinha dois servidores lá e percebi que, embora todos os verificadores de spam / listas negras tenham passado, o link me disse que o SPF era "Erro ao analisar os dados do SPF "
Eu removi um e deixei apenas o google, e parece estar funcionando agora