There is a DNS timeout that's happenning. When PHP connects to Sendmail to deliver the message, Sendmail is looking up either (A) the IP of the sender's domain, (😎 the IP of the recipient's domain, (C) the host name of the sender's IP, or (D) the host name of the recipient's IP. The DNS resolver that Sendmail uses is having trouble coming up with an answer, finally Sendmail times out and probably just delivers the message anyway.
This could be resolved by putting the required entry in your /etc/hosts table. Or any one of a number of tricks that sysadmin's use to solve such problems.
If you turn register_globals back on for just a minute (for testing purposes), does the mail go through quickly again? There shouldn't be any connection between register_globals and DNS timeouts.
You said you turned register_globals off a while ago. Is that the only thing you did? Or were you moving or reinstalling the server at that time?