Our application experiences exactly the same problem. I also tried both techniques you outlined below (AT+CCLK + AT!GPSXTRATIME) but the GPS fix times remain consistently poor.
In fact I’ve never been able to get the GPSXTRA features to download any almanac/ephemeris data at all, despite trying endless sets of configuration options. I think it’s because it doesn’t use the active PDP connection and instead tries to create it’s own, but it’s impossible to set the correct APN details for XTRADATA.
I’d be very interested if you ever find a solution / workaround.