When default configuration is used (so A-GPS is enabled, nRF Cloud is used) with asset_tracker_v2 (https://github.com/nrfconnect/sdk-nrf/tree/master/applications/asset_tracker_v2), then getting GPS gets fix after 1 to maybe 20 minutes (it is random). When A-GPS is disabled (all CONFIG.*AGPS.* are set to 'n'), then GPS never gets fix. The default GPS timeout is quite short (60s), so it was extended to 300s. Unfortunately, this change didn't help.
When GPS sample (https://github.com/nrfconnect/sdk-nrf/tree/master/samples/nrf9160/gps) is used with default configuration (which is without A-GPS), then GPS gets fix within 15-60s after reboot and this is reproducible. I would expect the same (or slightly worse, but at least reproducible/deterministic) behavior with asset_tracker_v2 application and disabled A-GPS.