Jeg vil give dig et vildt gæt her:Database caching.
Første gang du udfører siden, er forespørgslen ikke cachelagret i databasen, så det tager længere tid, og dermed udløber PHPs tidsfrist.
På de andre gange er forespørgslen meget hurtigere.
Du kan enten opdele forespørgslen, som du nævnte, eller du kan prøve at øge tidsgrænsen på scriptet:
set_time_limit(0); //No time limit
set_time_limit(60); //60 seconds
For at være sikker kan du bruge dette at rense databasecache og altid bruge den, så du altid vil køre siden på ren cache.