Embora os serviços on-line estejam fora do tópico no Superusuário, isso pode ter uma causa mais genérica: a filtragem de spam baseada em Registros SPF , fazendo com que receber servidores de e-mail rejeitem sua mensagem caso seu domínio tenha indicado que o e-mail deve ser enviado apenas de determinados endereços IP.
Você pode usar algumas ferramentas on-line para ver se seu domínio usa registros SPF. Em caso afirmativo, o melhor é enviá-lo por e-mail através dos endereços IP listados nesses registros. Portanto, ao usar o Gmail no Mail.app, use também o servidor SMTP do Gmail, não o servidor do seu próprio provedor. Quando seu próprio domínio ou e-mail comercial usa SPF (talvez através do Google ), você pode ser necessário usar algum servidor específico também.
Serviços on-line baseados em e-mail para testar o SPF também estão disponíveis .
Além do SPF: talvez você esteja usando um endereço IP compartilhado de alguma forma na lista negra ?