É normal nos depararmos com problemas no serviço de e-mail, mas geralmente eles são produto de uma configuração equivocada.

Em primeiro lugar, é importante ressaltar que o serviço de e-mails precisa de certas configurações de DNS para poder funcionar corretamente, para que as mensagens encontrem seu caminho na internet.
Verifique que as configurações de MX e SPF do seu domínio estão corretas, utilizando uma ferramenta como essa aqui para teste, colocando seu domínio e escolhendo a opção MX e logo a opção TXT. O resultado deve ser similar a esse:

Caso o resultado esteja diferente, verifique esse tutorial para configurar de forma correta.

Mensagens de certos domínios remetentes sempre caem na minha caixa de SPAM

1. Esse problema costuma ser porque o SPF do remetente não está configurado de forma correta. Verifique o passo "Não recebo mensagens de um remetente específico no meu e-mail"