Are you sharing your location? Maybe nothing is stored, but your current location is used for searches you make.

I've had the same results when I've explicitly not shared location.

I will also use Google maps to find the route to some restaurant, turn off the GPS because I don't like being tracked and it's no too far, then head to the restaurant within 10-60 minutes of when I checked the GPS. If I have wifi on I will invariably get asked to rate the restaurant within 5 minutes of arriving there, regardless of how much time has passed since I checked the route.

I currently use a Pixel phone, but based on the experiences I've had, I will be switching to an iPhone in the hope that I get tracked less. After switching to Firefox and ddg as my daily drivers, I just need to get off of Gmail and I will be google free

I would recommend Lineage for a Google-free Android experience.

Don't forget replacing all G logins with custom ones to various places. https://myaccount.google.com/permissions

Are you turning off GPS or all location? Because location can still be enabled when GPS is off. There's location via wifi and via bluetooth.

The location option in the android quick menu. I was unaware there was any other way to even turn off the GPS. I assumed it was wifi since it seems to not happen when the wifi is turned off.

It would have at least been corporate speak to have an option called GPS that people assumed was location tracking and was not. Having an option called "Location" that does not stop your phone from tracking your location when turned off has crossed the line into fraudulent behavior for me

Hmm, that seems to completely turn off all location. So I don't know why google would seemingly still know your location.

All they need to do is see what wifi connections I can reach on my phone. In any urban area you can easily reach 50+ wifi connections standing in one spot. If google knows X wifi connection corresponds to Y range of a physical location because of someone else left their location and wifi on, then they can tell that if I can reach 4 or 5 different wifi connections at once then I must be at a certain address.

It's like browser fingerprinting. It doesn't take very many bits of entropy before you are identifiable

Yeah, I know about using wifi for location. But I think turning the android location setting off disables that (in addition to disabling gps and bluetooth location). These pages indicate that:

https://support.google.com/android/answer/3467281

https://support.google.com/android/answer/6179507

I'd have given you that as a fair point if it hadn't said "x minute drive - home" next to the pin while I was checking a store's location on my work laptop at work (while signed in to my personal account)

Are you saying google's looking at your current location? That sounds to me like it's saying the store is an x minute drive from your home. It says nothing about your current location (work).

"Deleted the address, kept the coordinate pair" ;)

The true reason is probably a little less cheeky: keeping track of copies is hard. And here we end or digression into apologetics and return to criticism, ensuring correctness in keeping track of copies is surely not a very high priority.

If you download your maps data from Google you will see the address is still saved as it was before (in json format).

So the address is still there, they are just actively blocking you from making use of it in most of their apps (but evidently not all of them, as you noted above).