The first thing to check for long delays when doing network requests is dns issues. Try some dns lookups on your machine, for example
nslookup otherserver.foo.com. On the remote machine, try the same lookup of your local machine. Try doing dns lookups of the ip address and see if something is wrong with reverse lookup.
Does this delay happen if you send a mail directly on the machine, i.e.:
mail -s "test message" firstname.lastname@example.org </dev/null
I don't know how the php mail() function works. You need to figure out how exactly it is calling sendmail on the machine - is there something about the way it does that which causes the sendmail process to send the maiul but then sit there doing nothing for a long time afterward?
/var/log/messages on your machine to see if there are any interesting sendmail messages in the logs.