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