Courriels qui n'arrivent pas à destination, en sortie ou en entrée

Bonjour,

J'ai acheté mon nom de domaine et je suis hébergé par une structure assez sérieuse mais plus petite qu'OVH.
Mon problème est que j'ai appris que des courriels m'avaient été envoyés sans que je les reçoive (adresse orange) – je précise que j'ai désactivé l'anti-pourriels –, et que certains courriels envoyés par moi n'ont pas été reçus (serveur privé, avec des problèmes pour cet exemple, mais je soupçonne d'autres non-réceptions). Tout ceci est aléatoire : avec les mêmes adresses, sauf exception cela marche.
J'ai remarqué aussi parfois des lenteurs à la réception (réception dix heures plus tard une fois).

Ma question est : est-ce une fatalité ?

Je vois deux options possible, sans savoir si ce sont des solutions à mon problème :
1) Changer d'hébergeur pour aller chez OVH, qui est une boite plus costaud (à moins que vous connaissiez un hébergeur plus sûr…). Mais le problème vient-il vraiment de là ? Changer d'hébergeur, c'est compliqué le temps du transfert, et OVH a un service client qui fait peur à vrai dire.
2) Changer pour une adresse Gmail. J'ai tout le temps essayé de fuir Gmail, mais je demande si ce n'est pas le service le plus sûr au niveau assurance de transmission de message. Je sais que Yahoo, Free, ... il y a beaucoup de problème. Jamais entendu pour eux. Mais cette solution ne m'enchante pas.
À moins qu'à chaque fois, c'est la faute de l'autre adresse, et que je ne peux rien y faire... J'utilise vraiment beaucoup les courriels, et je voudrais la solution la plus sûre possible.

Merci d'avance.