No queda duda, es cosa del hosting. Creo que utilizando un servidor SMTP funcionaría. Si no, como último recurso, puedes mirar las faqs del hosting, donde te dan algunas
alternativas .
Tienes ejemplos de como funciona en la propia página de
PHPMailer.
Un saludo :)