Se non riuscite ad inviare posta e tra i log di postfix (mail.log, etc) vedete:

Nov 20 14:38:48 mail postfix/smtpd[26826]: NOQUEUE: reject: RCPT from unknown[123.123.123.123]: 450 4.1.2 : Recipient address rejected: Domain not found; from= to= proto=ESMTP helo=

molto probabilmente il problema è nel fatto che postfix non riesce ad effettuare la risoluzione DNS del dominio indicato nel log.

Facendo delle prove ho notato che nel mio caso il problema era proprio quello, ma pur modificando i server DNS nel classico file /etc/resolv.conf le cose non cambiavano. Controllando la documentazione mi sono accorto che postfix crea una copia del file resolv.conf in /var/spool/postfix/etc/.
Pertanto, il nuovo file /etc/resolv.conf va copiato anche in /var/spool/postfix/etc/resolv.conf

enjoy