I wouldn't say GPS was "required" that long ago, but the market pressured were making it so. I was building control plane assisted GPS software for the e-911 mandate in 2004, a time when Moto had iDEN. Those phones had a chip that you could "turn off" in the UI except, of course, I could still query it via the network and pull a location.
When I was writing locative software in Africa a big issue was that the burner phones didn't have GPS chips in them since they were so cheap. No worries, we just trilateral end their position and kept historical records of their movements so as to predict their patterns. Several drug dealers could attest to that but you'll have to go ask them in the afterlife.
We also had a Stinger. In 2009, and were listening to encrypted cellular conversations based on the ESN in 2006. Anyone who thinks they have privacy with a cell phone needs to buy some oceanfront property in Arizona.