É 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 caindo na caixa de SPAM dos destinatários:

1. Em primeiro lugar verifique se suas configurações DNS estão corretas, seguindo esses passos.
    
2. Se o envio está sendo efetuado usando outra ferramenta, como Sendgrid por exemplo, verifique esse tutorial para garantir a correta configuração do seu SPF.
3. É possível que a mensagem esteja sendo qualificada como SPAM devido ao seu conteúdo. Nesse caso, recomendo que utilize a ferramenta Mail Tester, clicando aqui. Basta enviar a mesma mensagem que está caindo na caixa de SPAM dos seus destinatários para o endereço de e-mail mostrado na tela do Mail Tester e logo clicar em "Verifique sua Pontuação". A ferramenta mostra um relatório com todos os problemas.