Fuente: http://www.howtoforge.com/postfix_relaying_through_another_mailserver
A veces nos rechazan los correos porque al tener IP dinámica entran en listas negras, etc…
Lo mejor es usar un servidor de correo externo SMTP, por ejemplo el que nos da nuestra conexión a internet.
Es lo que se llama relay en otro servidor:

1. Instalamos postfix y otras cosillas

aptitude install libauthen-sasl-perl libsasl2-2 libsasl2-modules postfix

2. Teclear 'y' + 'enter'

3. Teclear 'y' + 'enter'

4. Seleccionar 'sitio de internet', seleccionar 'aceptar' y pulsar 'enter'

5. Teclear el nombre que tendrá el remitente de los correos enviados desde esa máquina, seleccionar 'aceptar' y pulsar 'enter'

6. Por si las moscas desinstalamos (si lo estuviera) exim4

aptitude purge exim4

7. Lanzamos los siguientes comandos:

postconf -e 'relayhost = smtp.servidorexterno.es'
postconf -e 'smtp_sasl_auth_enable = yes'
postconf -e 'smtp_sasl_password_maps = hash:/etc/postfix/sasl_passwd'
postconf -e 'smtp_sasl_security_options ='
echo "smtp.servidorexterno.es   usuario:contrasenya" > /etc/postfix/sasl_passwd 
chown root:root /etc/postfix/sasl_passwd
chmod 600 /etc/postfix/sasl_passwd
postmap /etc/postfix/sasl_passwd

Cuando enviemos un correo, por ejemplo desde la linea de comandos:

echo "cuerpo del mensaje" | mail -s "asunto" cuenta@dominio.com

Podemos comprobar en el log:

cat /var/log/mail.log

Salida:

Nov 27 01:27:54 maquina postfix/pickup[4730]: 5655B3ED4: uid=0 from=<root> 
Nov 27 01:27:54 maquina postfix/cleanup[4819]: 5655B3ED4: message-id=<20081127002754.5655B3ED4@maquina> 
Nov 27 01:27:54 maquina postfix/qmgr[4731]: 5655B3ED4: from=<root@maquina>, size=316, nrcpt=1 (queue active) 
Nov 27 01:27:54 maquina postfix/smtp[4821]: 5655B3ED4: to=<cuenta@dominio.com>,relay=smtp.servidorexterno.es [62.14.3.192]:25, delay=0.45, delays=0.02/0.01/0.29/0.14, dsn=2.0.0, status=sent (250 OK id=1L5Udy-0000f3-Rx)
Nov 27 01:27:54 maquina postfix/qmgr[4731]: 5655B3ED4: removed 

Está probado y funciona, pero el procedimiento paso a paso se perdió, así que lo que aquí consta habría que comprobarlo.

Respecto al procedimiento anterior, dos diferencias:

1. Se necesita instalar un paquete adicional:

aptitude install libgnutls26

2. Detecto que cada X tiempo hay un error de autentificación. Si voy a la interfaz web, la contraseña es correcta, pero me pide un kaptcha, que al ser introducido, vuelve a dejar 'via libre' para el envío de correos desde linea de comandos.

Veamos en el log (/var/log/mail.info) dos ejemplos:

Correo no enviado por error de autentificación:

Mar 29 06:27:51 nombre_local postfix/qmgr[458]: 0EB085531B: from=<FaxMaster@dominio_local>, size=17250, nrcpt=1 (queue active)
Mar 29 06:27:51 nombre_local postfix/smtp[3379]: setting up TLS connection to smtp.gmail.com[74.125.79.109]:587
Mar 29 06:27:51 nombre_local postfix/smtp[3379]: certificate verification failed for smtp.gmail.com[74.125.79.109]:587: untrusted issuer /C=ZA/ST=Western Cape/L=Cape Town/O=Thawte Consulting cc/OU=Certification Services Division/CN=Thawte Premium Server CA/emailAddress=premium-server@thawte.com
Mar 29 06:27:51 nombre_local postfix/smtp[3379]: Untrusted TLS connection established to smtp.gmail.com[74.125.79.109]:587: TLSv1 with cipher RC4-MD5 (128/128 bits)
Mar 29 06:27:52 nombre_local postfix/smtp[3379]: 0EB085531B: SASL authentication failed; server smtp.gmail.com[74.125.79.109] said: 535-5.7.1 Username and Password not accepted. Learn more at                   ?535 5.7.1 http://mail.google.com/support/bin/answer.py?answer=14257 7sm3944467eyg.47
Mar 29 06:27:53 nombre_local postfix/smtp[3379]: setting up TLS connection to smtp.gmail.com[74.125.79.111]:587
Mar 29 06:27:53 nombre_local postfix/smtp[3379]: certificate verification failed for smtp.gmail.com[74.125.79.111]:587: untrusted issuer /C=ZA/ST=Western Cape/L=Cape Town/O=Thawte Consulting cc/OU=Certification Services Division/CN=Thawte Premium Server CA/emailAddress=premium-server@thawte.com
Mar 29 06:27:53 nombre_local postfix/smtp[3379]: Untrusted TLS connection established to smtp.gmail.com[74.125.79.111]:587: TLSv1 with cipher RC4-MD5 (128/128 bits)
Mar 29 06:27:54 nombre_local postfix/smtp[3379]: 0EB085531B: to=<cuenta@dominio.com>, relay=smtp.gmail.com[74.125.79.111]:587, delay=248170, delays=248167/0.01/2.7/0, dsn=4.7.1, status=deferred (SASL authentication failed; server smtp.gmail.com[74.125.79.111] said: 535-5.7.1 Username and Password not accepted. Learn more at                   ?535 5.7.1 http://mail.google.com/support/bin/answer.py?answer=14257 10sm3981758eyd.3)

Correo enviado correctamente:

Apr  3 09:45:02 nombre_local postfix/pickup[28227]: 41FB3550EB: uid=10 from=<FaxMaster>
Apr  3 09:45:02 nombre_local postfix/cleanup[28307]: 41FB3550EB: message-id=<20090403074502.41FB3550EB@nombre_local.localdomain>
Apr  3 09:45:02 nombre_local postfix/qmgr[458]: 41FB3550EB: from=<FaxMaster@nombre_local.localdomain>, size=1305, nrcpt=1 (queue active)
Apr  3 09:45:02 nombre_local postfix/smtp[28309]: setting up TLS connection to smtp.gmail.com[72.14.221.109]:587
Apr  3 09:45:02 nombre_local postfix/smtp[28309]: certificate verification failed for smtp.gmail.com[72.14.221.109]:587: untrusted issuer /C=ZA/ST=Western Cape/L=Cape Town/O=Thawte Consulting cc/OU=Certification Services Division/CN=Thawte Premium Server CA/emailAddress=premium-server@thawte.com
Apr  3 09:45:02 nombre_local postfix/smtp[28309]: Untrusted TLS connection established to smtp.gmail.com[72.14.221.109]:587: TLSv1 with cipher RC4-MD5 (128/128 bits)
Apr  3 09:45:05 nombre_local postfix/smtp[28309]: 41FB3550EB: to=<cuenta@dominio.com>, relay=smtp.gmail.com[72.14.221.109]:587, delay=3.1, delays=0.05/0.01/1.5/1.6, dsn=2.0.0, status=sent (250 2.0.0 OK 1238744926 d6sm3590039fga.17)
Apr  3 09:45:05 nombre_local postfix/qmgr[458]: 41FB3550EB: removed

Hay que ir revisando este tema