That sounds a lot like the time required to acquire the complete almanac from the GPS signals. See the almanac section of:
http://en.wikipedia.org/wiki/GPS_signals
If a GPS receiver has no current satellite orbit data, it'll need to listen for 12.5 minutes to determine the current set of satellite orbit information.
There's a useful explanation of the various possiblilities of GPS startup (specifically talking about Garmin models and terminology, but more broadly applicable too) here:
I guess that it searches each time for new satellite signals if the last usage of GPS was too long ago.