Well, the script runs and terminates, and the email is eventually delivered, so PHP is not at fault (unless it turns out to be a incorrect header or something, but I would imagine it would either bounce or go right through, not be delayed.)
So it's either a problem with the mail server (such as a disk space issue or an overloaded outgoing queue) the link between the source and destination (for example a poor connection with packet loss on your end, their end, or between; SMTP keeps timing out on delivery) or a problem with the receiving mail server (again, disk space, server load, or localized network issue)
But if it's taking a long time no matter where the user is, then it's probably a problem on your server. It's hard to be much more helpful without details. Do you own/run/operate the server? What mail server package do you use?