E' proprio nelle specifiche dell'hosting? Oppure ci sei arrivato provando da un altro hosting?
Potrebbe essere che dall'hosting dove hai il sito sia partito in passato un sacco di spam e il loro mailserver sia stato messo in qualche blaklist.