"SPF" é um registro que indica através de quais IPs um domínio pode enviar emails. O Gmail passou a obrigar que todos domínios declarem seus SPFs, a fim de evitar emails forjados, ou seja, você deve declarar os IPs dos nossos servidores de email, para que eles estejam autorizados a enviar e-mails do seu domínio para outros servidores.

O erro, no caso de não ter SPF e nem DKIM (outro tipo de validação com chave encriptada), é algo aparecido com este, no caso, do Gmail, quando recebem um email de um domínio sem SPF:
A maior parte dos nossos clientes não sofre com este erro, pois sempre criamos SPF em todos os domínios criados em nosso DNS e, caso use servidores de DNS externos, em nossa mensagem de boas-vindas, explicamos a importância de se criar esse registro. O problema costuma ocorrer caso use DNS próprio (registro.br, Cloudflare ou outro) e não crie esse registro.

Veja no seguinte tutorial, como criar o registro TXT de SPF: https://suporte.lucanet.com.br/kb/outros/entradas-de-dns-do-servico-de-email

O SPF já é suficiente, mas é sempre bom também criar um DKIM. Detalhes em: https://suporte.lucanet.com.br/kb/painel-de-e-mails-do-admin/como-configurar-dkim