Encontrei uma solução e, no final, adicionei o IP do servidor de e-mail ao registro TXT e agora o gmail aceita o remetente. Se alguém estiver interessado, é assim que parece:
v=spf1 ip4:xxx.xxx.xxx.xxx include:mailgun.org ~all
Eu uso mailgun e um servidor de e-mail namecheap (onde também tenho meu domínio) e quando recebo e-mails em minha conta do gmail, o mailgun é reconhecido como um remetente permitido, mas esse não é o caso do namecheap. É o que eu recebo:
Recebido-SPF: softfail (google.com: domínio da transição xx @ mydomain não designa ... como remetente permitido)
Eu tenho o seguinte registro TXT no meu DNS
v=spf1 mx include:mailgun.org ~all
É um IPv4 e eu leio algumas outras mensagens no serverfault sem sorte, então qualquer pensamento sobre isso será apreciado.
EDITAR
Como afirmado aqui , o e-mail privado do Namecheap configura os registros MX automaticamente e eles não são mostrados na lista de registros do DNS, acho que isso tem algo a ver com o fato de que ele não foi reconhecido como um remetente permitido quando eu tinha o Registro MX no spf.