@Selkie: I am sorry, maybe I have simply not made the point clear enough.
If you speak in a language that assigns a gender to a noun, this gender is like "glued to" the image in your head. In my previous example, it was not about the formality to learn the gender together with the noun, but to really incorporate it into the image in you head.
That's also the same strain of thought as in #6:
If your conversation explicitly included the word "Baum" in German, and all of a sudden, the person you were talking to is speaking of "sie", then it is simply correct to be confused, even as native speaker :D because he is simply changing the gender within a conversation - and then it's simply "his fault" ;) The same goes for your second example: If you're searching for your digital camera and say, "Ich finde meine Kamera (sie) nicht." And, 2 minutes later you say, "Hast du ihn gesehen?", every native speaker will either react by asking "Hab ich WAS gesehen?", or requires a 'moment of clarity' to conclude that you actually meant the same as before.
If you have not had the word "Baum" in your conversation before, it is a simple misunderstanding and also requires a moment to switch, because you both got different images in your head, i.e., the two images need to be aligned first.
Anyway, to answer your question from the beginning: it is simply part of being a German speaker. On-spot communication, as they say in marketing departments ;), is better be part of it, too.
Yes, it may be grammatically correct, but "Mädchen" (in contrast to "der Junge") is a special case. As irritating as it may sound, it's usually better to say "Das Kind/Baby" because small-talk conversations about childen are not about stressing the gender, or differentiating sexual orientations at that age. If you want to do that, or be more specific for whatever other reason there is, you could always say sth. like, "Was macht die Kleine/der Kleine denn?" (der/die Große as well). The second is in a way more "intimate" than the first, more like you already know that little rascal ;) or want to sound a bit more personal.
With girls, it's a different matter. If you're standing in a crowd and some girl catches your eye, you would neva say "Das da drüben gefällt mir." That may be grammatically correct, but is simply offensive, degrading a girl to an object, actually. In addition, girls have names ;) and if you're talking about a certain girl whose name has already come up, you also say SIE (female) in contrast to ER (male) and never ES. That has something to do with the two reasons I mentioned in the paragraph above.
Hope that helps.