De toute façon, hébergement mutualisé et envoi de mails, ça n'a jamais fait bon ménage.
Vu que tous les hébergés partagent la même adresse IP pour leur site, ils partagent aussi la réputation de cette IP et les éventuels blacklistages des acteurs de la lutte anti spam.
L'idéal, c'est d'avoir sa propre IP et ce qu'on appelle un enregistrement DNS PTR, impossible en mutualisé.
Sinon, dans le pire des cas, tu peux utiliser des services externes pour faire transiter tes mails. Tu as Sendgrid ou ElasticEmail qui proposent des formules gratuites.
A une époque, n'ayant pas cet enregistrement PTR parce-qu'on était 2 sur un serveur, j'utilisais Sendgrid sans aucun souci (c'est plusieurs milliers de mails gratuits / mois) .