> Now (Google says) your devices each store their own location history without centralisation.

...I smell a "backdoor" that's in the shape of the "Locate my device" and similar such systems. Unless there's no Android subsystem that will dredge up and present info about where a phone has been, then this demand seems totally plausible:

"We know that you can cause a device to report its historical location information. Cause all of the devices that were within area X between times T and G to report their positions during that time to us, the police. Here's our warrant."