Revisa los logs de Sendmail para ver si encuentras el origen del problema.
O utiliza un servidor SMTP externo. Parece ser que con Gmail (Google) puedes hacerlo y además gratis. Encontré estas instrucciones, aunque en inglés:
http://lifehacker.com/111166/how-to-...ur-smtp-server