nel primo post e in un altro c'è una contraddizione e non ho capito la situazione: ad altri domini dello stesso server funziona o no? è importante perchè:

1) se invia solo al di fuori del server è un problema legato ad esso (p.es. all'ip)
2) se invia solo ad altri domini è un problema legato al nome di dominio

potrebbe esserci qualche regola nella gestione della posta... hai un pannello di amministrazione (tipo cPanel, Plesk, altro...), per caso?