There maybe a couple of different factors in play here.
GPS & UTC
First is that as you point out GPS time is different to UTC. GPS has a message that advertises the current offset from UTC, see here. It's possible that not all GPS chips in mobiles pay attention to it, or haven't yet received the GPS offset message yet at the moment you're asking for GPS time data.
Unless there is support in the Android API for discovering this sort of condition you will be reduced to interpreting the NMEA sentences yourself (I don't know if Android makes them available), and even then it will depend on exactly what the manufacturer has decided to put in to those sentences.
According to this PDF, it can take up to half an hour for the complete almanac data to be received by a GPS receiver. The almanac contains the current GPS/UTC offset.
My guess is that because mobile GPS chips are built around AGPS (assisted GPS), they're probably expecting to get GPS almanac data fed to them sourced from a cellular network and might not be too clever at retaining or receiving almanac data for themselves.
So if you're out of range of WiFi and mobile phone networks (you say you cannot use network synchronisation to get time of day...) it might take anything from 12.5 minutes to half an hour before the phone's GPS chip starts giving you UTC time instead of GPS time.
That's a long time for a mobile's GPS chip to be switched on. I'm guessing that often they're not powered up by the OS long enough to ever receive the whole almanac.
If this is indeed the cause of your problem then you may be sunk. GPS almanac data doesn't change very often AFAIK, so you might be able to cache it yourself and somehow supply it to the OS / GPS somehow in leiu of it being read from a local cell basestation. That's starting to sound awfully low level though, and I doubt that Android supports that kind of almanac injection (it's a horrendous denial of service opportunity for malware...).
Clock Drift
The other less likely factor is that the mobiles aren't necessarily running an NTP client in the same way a desktop can. Most Linux desktop distros install an NTP client that constantly runs in the background keeping the local clock in step with some NTP server somewhere. Mobiles (including AFAIK Android) generally don't need that level of time accuracy, so they correct their clock quite rarely in the interests of saving battery life, so it is possible for plenty of drift to accumulate. However I would be surprised if it got as bad as 15 seconds, so it might not be due to this.