My Location History and Web & App tracking are off, and I'm still able to use my Home and Work addresses on Google Maps.
I see many people here have your same experience, which is pretty odd to me. I live in Israel, maybe there's a connection somehow?