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 mail, por ejemplo desde la linea de comandos (para finalizar poner un “.” e intro):

# mail jose@legido.com
Subject: Hola
Adios
.
Cc:

Veremos en el log:

/var/log/mail.log

Nov 27 01:27:54 quixot postfix/pickup[4730]: 5655B3ED4: uid=0 from=<root> 
Nov 27 01:27:54 quixot postfix/cleanup[4819]: 5655B3ED4: message-id=<20081127002754.5655B3ED4@quixot> 
Nov 27 01:27:54 quixot postfix/qmgr[4731]: 5655B3ED4: from=<root@quixot>, size=316, nrcpt=1 (queue active) 
Nov 27 01:27:54 quixot postfix/smtp[4821]: 5655B3ED4: to=<jose@legido.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 quixot postfix/qmgr[4731]: 5655B3ED4: removed