Mon hébergeur déconseille l’utilisation de plusieurs serveur mx en même temps.
Car comme tu l’as mentionné les mails peuvent transité soit par l’un ou l’autre sans reel raison.
Et il m’en a pas dit plus 
non plus.
Après mon avis perso l’hébergement perso de mail pourquoi pas mais pas pour du pro.
Pas étonnant, c’est le principe du MX secondaire En indiquant un “nombre” plus élevé dans le champ MX, on indique une priorité plus faible. Les serveurs expéditeurs bien élevés vont donc toquer à la porte du premier MX, et s’il ne répond pas, passer aux suivants dans l’ordre décroissant de priorité.
Une façon simple de récup’ les mails qui se trompent de MX : mettre un transfert automatique de la “boite de secours” vers son adresse principale ou un alias…
Un souci vis-à-vis de cette configuration : la gestion du spam. Cf ce billet de Stéphane Bortzmeyer.
Salut,
j’héberge mes emails sur un VPS depuis 1 an. Au début, je n’avais aucun problème, mais récemment, de plus en plus de domaines me classent comme spam. J’ai fait une demande whitelist pour gmail et cela semble avoir fonctionné. https://support.google.com/mail/bin/request.py?&contact_type=msgdelivery
Aussi je viens de faire une demande ici: https://www.dnswl.org
On verra…
Merci pour ce lien qui confirme un peu ce que j’avais pressenti en essayant rapidement de mettre en place un MX secondaire sur mon serveur (très naïvement et sans réfléchir aux diverses conséquences). Dans le cadre d’un email perso ou familial ça semble créer plus de problèmes que ça n’en résoud…
Ah étrange comme je l’expliquais plus haut ça me fait exactement le contraire. J’ai l’impression que le temps “bonifie” la réputation de mon (micro) serveur. Ça n’empêche pas quelques accidents d’arriver de temps en temps, tu n’as peut-être simplement pas eu de chance avec gmail et dnswl qui t’ont kické au même moment.
As-tu jeté un coup d’oeil dans les logs et refait un mail-tester pour vérifier que tout va bien ?
Voici un extrait d’un mail de Talos que j’ai reçu ce matin:
IP […] has begun to improve and currently has a neutral SenderBase email reputation (within acceptable parameters). The reputation should continue to improve as we receive additional good mail volume reports for the IP from our sensor network.
Les logs sont bons pour autant que je sache. Tu as hébergé depuis longtemps ? Je pense qu’il ne me reste plus qu’à attendre 
Je crois être sur la même IP depuis maintenant 1 an et demi. Ça ne va que s’améliorant (et tant mieux!)
Dès que j’entends parler d’un système de whitelist je m’y inscris, cela y contribue peut-être.
Bon la conséquence de ça c’est que vu la galère je risque de rester chez le même fournisseur VPS pour un moment…
Hello,
À ta connaissance, tu te retrouves jamais dans les spams de Microsoft, Google ou Yahoo ?
Aussi, il serait peut-être bon de lister ici les services de whitelist sur lesquels tu t’es inscrit. 
Je suis heureux de voir qu d’autre personnes ont rencontré des problèmes avec ces entreprises. Pour moi avec un premier VPS chez OVH aucun problème. Par contre le second VPS chez OVH, j’ai une erreur d’envoi sur les adresses hotmail.fr et je finis constamment dans les SPAM Gmail.
J’ai l’impression que c’est complètement aléatoire et gratuit, voir même méchant.
Pour les histoires de spam, c’est à mon avis pas vraiment lié à l’hébergeur, en premier lieu il faut vérifier ce que le diagnostique te dis et si il n’y a pas des éléments restant à configure (DNS / DKIM / reverse DNS / blacklist, etc …)
Il se peut que l’IP qui t’as été attribuée ait été “pourrie” par un ancien locataire de l’IP et soit donc dans des blacklists, mais là encore la faute n’est pas réellement sur l’hébergeur mais sur le système de blacklist de l’écosystème mail qui est très discutable … (que ce soit les blacklists “publiques” genre RBL, ou les blacklists internes de Google/Microsoft)