Justement leur serveur n'a pas de nom, nous avons été obligés de créer des sous-domaines en A pointant vers l'adresse IP de leur serveur de mail pour ensuite faire pointer le MX du nom de domaine vers ces sous-domaines étant donné qu'un MX ne peut pas pointer vers une IP, il n' y a rien d'anormal à ça et ça fonctionne.
 
Sinon pour info, le problème est à priori résolu, j'ai contacté le fournisseur du serveur de mail de notre client et lui ai demandé de changer le greeting. Depuis le client nous a téléphoné pour nous dire que maintenant ça fonctionne.
Ce qui est plutôt anormal, c'est que ce soit nous qui soyons obligés de résoudre ce problème alors que le soucis venait de l'autre fournisseur, mais bon, vive le monde des entreprises.