The outgoing SMTP server that you are using with phpmailer may be tarpitting you. To test, from the host where php is running, try opening a telnet connection to the SMTP server on port 25. It should respond with a HELO or EHLO command immediately. Does it, or is there a delay?
After it responds, proceed the SMTP session as per the instructions at http://www.port25.com/how-to-check-an-smtp-connection-with-a-manual-telnet-session-2/. If there is a delay after any command, this is known as 'tarpitting'. Tarpitting is used by some mail servers to catch other mail servers that may be spamming (i.e. sending commands before they should) or to slow down mail servers that try too many messages in too short of a time.