Seems a problem with your sendmail.
Can you do a "telnet localhost 25" from your shell ?
If the server answers slow (like from php) you or your administrator must configure correctly the sendmail.
Anyway, you can use any smtp class for send mails throw other smtp server.