Quano invii una e-mail da un server di posta, questo deve poter risolvere i nomi dei server MX del dominio. Ad esempio se spedisci a qualcosa@libero.it, il server deve individuare l'indirizzo del server (in questo caso sono più di uno) che accettano la posta di libero.it e lo fa utilizzando un DNS.

Una alternativa, e mi sembrerebbe il tuo caso, è inviare le e-mail ad un server smtp noto, in questo caso il DNS non serve se usi l'indirizzo IP del server al quale ticolleghi. La risoluzione dei nomi sarà un problema del server a ciu mandi la posta. Si parla di relay ed occorre avere permessi, basati su IP o autenticarsi.
# sendmail[28984]: AUTH=client, relay=smtp.gmail.com [74.125.137.109], authinfo failed
A leggere la prima riga dei messaggi che hai postato, sembrerebbe un problema di autenticazione a gmail.com che stai usando come relay smtp.

Qui: http://www.rfc.it/content/postfix-smtp-relay puoi trovare alcune note relative a postfix. Sendmail non è molto diverso.