Depois de alguns dias de pesquisa, consigo fazê-lo funcionar.
Eu adicionei outro failover de IP (intervalo IP diferente) no meu servidor e agora funciona.
Acho que o Google tem sua própria lista negra e o proprietário anterior do meu IP provavelmente estava enviando spam. Quando eles dizem que o conteúdo está relacionado, isso não é verdade, porque eu estou enviando exatamente o mesmo e-mail com o SPF errado e o inverso errado, então ele é totalmente relacionado ao IP.