The phone was fixed to the car's front window with plenty of sight towards the sky. I rebooted the device twice but it didn't help.
Our natural instinct here is to blame the russians for these kinds of things. At this time our biggest military exercise since the 90s was taking place in this region, with a lot of US involvement: https://en.wikipedia.org/wiki/Aurora_17
(One random theory: the russians were trying out some kind of remote, localized target GPS jamming tech. The GPS outage stopped once I got closer to the largest city in the region (150k people).
Additional rationale: If they unleashed GPS jamming signals that made hundreds of thousands of people lose GPS it would probably have made news. By localizing it to just affecting a couple of hundred people in isolated areas they would avoid that kind of mess.)