É 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.

Todas as mensagens que recebo caem na caixa de SPAM

1. Se sua conta for Exchange, clique em configurações (engrenagem no canto superior direito do webmail) > opções > bloquear ou permitir e cheque se a opção “Não confiar em email, a menos que o remetente seja alguém da minha lista de remetentes e destinatários confiáveis ou de remetentes locais” está desmarcada (essa opção quando ativada faz com que a maioria das mensagens caiam na sua caixa de SPAM).
2. Se você usa algum cliente de e-mail (como Outlook, por exemplo) ou tem o e-mail configurado no seu smartphone, é possível que alguma configuração esteja manipulando as novas mensagens. Troque a senha da sua conta de e-mail, sem atualizar o seu cliente de e-mail com a nova senha e teste o recebimento mais uma vez, verificando sua conta diretamente no webmail.
3. Cheque se existem regras de e-mail que possam estar manipulando as mensagens entrantes, colocando elas na caixa de SPAM. Clique aqui para acessar o tutorial sobre redirecionamentos.