Eh, I disagree, since a lot of times we rely heavily on visual cues to make assessments and determinations, and are often wrong just because of poor vision.
Take for example persons with androgynous features and the difficulty some people have with identifying them. Children are particularly useful for this insight since they are unabashedly curious and inquisitive, and it's not uncommon to hear a child blurt out "is that a boy or a girl?"; it would seem to me that their categorization process, even if not refined, gets goofed by androgyny; something as simple as hair length or facial hair greatly influences a child's ability to easily discern if persno is male or female.
At some level there is a categorization process that seems to happen with humans when it comes to recognition, we just assign high confidence to certain factors. In the case of children, it seems to be they look at person and use common factors like hair length, facial hair, and body shape to determine gender. The sound of one's voice also helps, but this usually isn't something we can pick up as easily or from afar in public places. As an adult, we probably have more refined points, but they are essentially the same as a child's point of view. Instead of "body shape" adults look for specific facial features, size of breasts, walking gait, style of clothing, hair style, etc. These are all just granular differences of how a child understands it.
This gets into personal experience, but when I was in college, I had long hair and really fine skin/facial features. All the time I would hear little kids ask "why does he look like a girl?" or "why does that girl have a beard?". I had no issue with their confusion, they were just curious kids. Something confused their understanding, and once it was explained "sometimes men have long hair", they just sort of accepted it.