I remember my French teacher saying that Madame or Mademoiselle was never used instead of Monsieur in the formal version of yours sincerely which I partially recalled & mentioned above but that was 21 years ago. Things might have changed like they have in other areas.A simple replace of "Monsieur" with "Madame", and no problem addressing women with it.
I have a problem with different French phrase: non-personal form of conjugation: "il pleut" (for "it rains") and all similar. Why do they use masculine pronoun "il" instead of neuter pronoun, e,g, "ça pleut" or "c'est pleut" ? I'm not a linguist to answer, because the reason for masculine pronoun usage here might be as old as French language itself.
I've no idea I'm afraid. You may be right.