bueno no estaria que te dieras una vuelta por /var/log/mail.log si es en debian y en redhat si mas no recuerdo es /var/log/mail , si estan instalados desde paquetes claro , depues de haber mandado el mail aunque no llegue te vas a esos logs y veras el porque , algo asi nunca me ha pasado pero si parecido ,tendras que recontruir el sendmail.cf en
LinuxParaTodos hay un buen articulo sobre un sendmail , yo por mi parte uso postfix es igual o mas eficiente y sencillo
Saludos