Se for um sistema em um endereço IP dinâmico, ele geralmente fica em listas negras - enquanto é opcional, acredito que o gmail usa uma lista de bloqueio que os inclui. Eu tive problemas o suficiente com isso que a execução de um servidor de e-mail em um endereço IP dinâmico não funciona.
Você pode querer verificar seus registros para confirmar isso - você geralmente recebe uma mensagem de retorno dizendo que as coisas estão bloqueadas.