Oh, that! Whenever I shave my head, I get called "Monsieur" all the time or "jeune homme" (young man). When parents tell their kids to move in the bus: "Move aside, the young man wants to pass." And then, when I thank them, they get all ill-at-ease, wondering whether they should have used a gender-neutral pronoun.
I can imagine how puzzled you feel when people still think you are of the other gender while you stand there, in front of them, making the ground slightly shake every time you open your mouth (I always imagined baritones being able to make the ground shake, for whatever reason).