But again, people use this even when I have no reason to know which store they went to.
I’m not necessarily saying they should stop doing this, but it’s clearly not the usual kind of definiteness implied but the use of “the”.
A prescriptivist pedant might insist that this is incorrect, and they should instead say "I need to go to a store", but in my judgment as a native speaker, the version with "the" is more idiomatic, and the version with "a" sounds stilted.
To repeat another part of my initial post, it's like the use of "the" in "the bigger they are, the harder they fall". It's clearly a different usage/meaning/sense of "the" -- in fact, most other languages use a different word for that sense. (German uses je ... desto.) It would be very dubious to explain all uses of "the" as "oh its when the noun has definiteness". It wouldn't cover that case, and it wouldn't cover (the typical use of) "I went to the store".
Some of the statements (by other people) in this conversation are wrong, based on applying a school-style oversimplified explanation that doesn't really match English usage.