Well after a bit more of reviewing the site (at least this morning) the PHP/MySQL appear to be operating at normal speed, i.e. very fast queries.
The time delay appears to be when the actual page is rendered back to the client. There are a few hops in between that are slow. So without more detailed analysis it could be the host provider or some site it's having to go through to get back to the client. Though odd that people in different locations around the World would get that if it was due to a hop in between, would seem to be more related to the host providers network in my opinion.
