Isso é muito difícil, se não impossível, solucionar problemas. Sem acesso aos logs do servidor de email, você só pode assumir qual é o problema.
Já tentou enviar o email para diferentes domínios? Talvez seja o final de recebimento que causa os problemas? Tenha em mente que o seu aplicativo de leitura de e-mail escolhe como exibir e-mails em HTML.
I just haven't run into a hosting company that literally -shrugs- off a problem like this
Na minha opinião, você deve procurar uma empresa de hospedagem diferente. Dizer "não há nada que possamos fazer" não é verdade, eles simplesmente não querem. Vá e procure uma empresa que possa ajudá-lo se você tiver problemas. Eles provavelmente não farão isso de graça, mas pelo menos você consegue ajuda.