Olá RafiWsky,
O MX do domínio tem que apontar para o mesmo FQDN que retorna se vc fizer uma consulta de DNS reverso para o endereço do MX. Ou seja, se vc consultar
host 189.112.139.141
vc tem que obter "ns2.dominio.com.br", e se vc consultar
host ns2.dominio.com.br
vc tem que obter "189.112.139.141". Do contrário, vc pode não passar em checagem SPF.
Fora isso, vc só tem que garantir que a porta em uso para o serviço SMTP está ativa e liberada para conexão externa --- às vezes não está, e a gente fica futucando, futucando, quando vai ver, o problema é na hospedagem.