ma quale mail server usi ? locale o remoto ?
non è un problema php ... prova ad impostare un altro mail server
esempio
usi ini_set('SMTP',mail.tin.it);