They are also long-lived ( on the scale of decades and centuries ) and have reasonably static names.
Yes, although in Soviet Union, they still often had other names and functions (as a movie theatre, or a grain warehouse, or whatever).
Some are - they are absolutely everywhere in all cities I've lived in or visited, and yet I couldn't tell you the names of more than a couple. Do people really know the names of a significant portion of them?
Probably the people who live in those neighborhoods do, which can be a useful reference if you're in those areas.
Asking people about churches in 198x USSR was probably not the wisest way to go around for a CIA spy. Better stick with libraries.
I was thinking more along the lines of "I'm looking for a shop near X."
Никогда ещё Штирлиц[1] не был так близок к провалу.