Algumas coisas.
1) Verifique se o registro PTR do servidor de e-mail está definido para refletir o mesmo que o seu registro MX, e não o mesmo que o nome do host do seu servidor.
2) Seu endereço IP parece ser um endereço IP do WebsiteWelcome / HostGator. Eu checaria com o apoio deles se você ainda não tivesse. É claro que o IP pode ser um antigo endereço IP deles que eles venderam de volta para o host, e você acabou de receber.
3) Se você é proficiente com tcpdump ou wireshark, você pode tentar capturar o e-mail do pacote enquanto ele sai e obter a resposta do servidor do gmail. Isso ajudaria mais do que os cabeçalhos.
4) Lembre-se de que o Gmail também trata o e-mail de todas as pessoas porque seus filtros de spam sabem que algumas pessoas consideram spam, outras não - por isso, é possível que você sinalize algo semelhante ao que está vindo do seu servidor como spam (mesmo que o conteúdo seja o mesmo que você está enviando através do cliente de email), e assim o Gmail está aprendendo sobre isso. Eu diria que tente usar um endereço de e-mail do Gmail diferente para testar essa teoria.
5) X-Get-Message-Remetente-Via: dom.domainbrokerage.co.uk: authenticated_id: grantw / from_h O problema aqui é que o authenticated_id não é um endereço de email. No cpanel, configure um endereço de e-mail dedicado que não seja a conta de e-mail principal da conta do cpanel.
6) X-PHP-Script: www.domainbrokerage.co.uk/admin.php para 95.172.231.27 O Gmail pode ver isso e bloquear com base nisso, mas é apenas um palpite. Se houver a possibilidade de remover esse cabeçalho, faça isso.
Espero que algumas dessas ajudas.