I personally don't feel a photograph with labels qualifies as a map, though it could be argued once labels were placed it was indeed a map. For me a map has to be created, by some means other than with a camera. That said, yes, as long as there is some labeled information in the region depicted, its a map. A map should contain a compass rose (or at least some directional device pointing to north or other singular known direction), and a scale of some kind, whether that is a grid with a known square size, bar scale or other means of depicting distance. Additional labels can be included as required for the purpose of a given map. As you say, as long some kind of useful data can be extracted from the pictorial information provided - its a map.

An unlabeled depiction of a given region is, at best, an unfinished map or at worst an image of some region of terrain only. You need to provide some additional labeling to qualify as a map, IMO.

A legend may be unnecessary, I seldom include one. I think a legend is especially useful when symbols on the map might not be universally recognized - upward pointing triangles representing mountains, for example. When I depict a mountain as a beveled shape depicting elevation rising, I might label a mountainous region as "X Mountain Range" which is enough for me to indicate this is a mountain. I don't need a separate box deliniating mountains, as there is more than one depiction, all the mountains may vary slightly as they are intended to appear as real mountains, and not as a singular symbol to represent a mountain. Since there is more than one version, each slightly different, a legend showing mountain symbol may not be so helpful. Especially when you are using brushes, with only single symbols for each landform or map location, then a legend is appropriate.

There are many kinds of labels and symbols that could be used on a map, but a map only needs scale and direction at the minimum to still qualify as a map, based on my definition above.