Controlla il file di log di sendmail se ci mette un minuto ad inviare la mail (a me succedeva così) è perchè non è configurato bene l'host.. quindi passa in modalità stand by per un minuto prima di tentare nuovamente l'invio (riuscendoci). Io non ho saputo risolvere il problema se non disinstallando sendmail (troppo complicato configurarlo) e installando qmail