Você deve configurar o servidor para usar um smarthost como um relé. Normalmente, seu ISP fornecerá um retransmissor para você usar.
Se você quiser enviar diretamente para a Internet, precisará de um endereço IP fixo com um registro PTR apontando para um registro A que retorna o endereço. Caso contrário, muitos servidores bloquearão você. Você também deve ter um registro MX para o domínio que você está enviando daquele ponto para o nome do seu servidor de email. O registro SPF para os dois domínios pode ajudar, a menos que eles proíbam o envio de seu servidor para esse domínio.
O Spamhaus lista muitos dos intervalos de endereços IP dinâmicos e você será bloqueado se o seu endereço IP estiver listado lá. Se você estiver listado em outras listas negras, provavelmente também será bloqueado.
Só porque o seu servidor de correio aceitou a mensagem para entrega, não significa que o seu servidor de correio será capaz de entregá-lo. Tente o comando mailq
para ver se o seu servidor ainda está tentando enviar a mensagem. E-mail é armazenar e encaminhar, e seu servidor pode demorar até um dia ou mais para informá-lo de que está tendo problemas para entregar o e-mail.
EDIT: A solução mais fácil é usar o comando dpkg-reconfigure exim4-config
e selecionar a opção smarthost. Use o relay de e-mail do seu provedor e as coisas devem funcionar bem. Certifique-se de usar um endereço de e-mail do remetente válido. Enquanto o GMail pode funcionar, é um esforço extra para configurar a autenticação necessária, e eles podem limitar a quantidade de e-mail que você envia se você não tiver uma conta paga.
Se você deseja executar seu próprio servidor de e-mail, comece com meu artigo sobre servidor de e-mail e execução . Você também pode querer revisar o meu documento Política de e-mail e os documentos que ele lista. Tenho várias outras postagens relacionadas ao e-mail. Meu servidor de escolha é o Exim.