As a German native speaker, I find the gendering of nouns something that happens absolutely automatic and with no thought whatsoever, like most other aspects of talking in a natural, un-forced manner. I daresay I cannot remember much of my Deutsch classes in school, but I cannot recall ever hearing of any rule, regularity, rhyme or reason for the gender of most words - it just is what it is. (I do not mean rules like "-er" or "-ling" usually being male, but a generic explanation for why a certain noun ended up with "-er" or "-ling" in the first place instead of ending up with a typically female suffix.)
From experience with my children, I cannot recall them mixing up the gender frequently when they were very small; presumably gender is learned together or inseparable with the meaning of the words.
As a side note, there are a very small amount of nouns whose gender seems variable based on dialect or region (e.g., "das Radio", "der Radio"), but that's not at all common. Also the gender for the same word might be different in different (but related) languages, like the moon being female in French, and male in German.
As to why a speaker may utter the correct combination of words/word endings even if it seems like they're searching for words mid-sentence, I can think of one reason: by some interpretations/theories, the thinking brain can be thought of to work in "modules" or "components".
One basic example would be one module which is a pure generator of thoughts - it just spews out random thoughts all day long with high frequency; and another module then acts as a filter and filters out thoughts which make no sense right now, and a third component which is conscious of thoughts. A setup like this would explain many aspects of our brain which we can often witness ourselves, for example, that when we're in a "flow state" with just the right intensity of problem solving, we are not aware of random thoughts (the filter filters out all thoughts not relevant to the problem at hand before they reach the "awareness" component). But if we are trying to sleep, and have no problem to solve, then the filter has nothing to filter by, and passes along random thoughts to our awareness.
The same could well be the reason for your phenomenon: there could be some component of the brain which wants to communicate something to the world, with a representation of objects in an abstract manner (i.e., not in the form of words), and a different component which translates the abstract thing into words. The abstract representation of the object might as well already contain the gender; so the "verbalization" stage already has the information that what's coming will be feminine even though it's still "looking up the word" in its "dictionary".
Note that I am using a lot of quotes here - treat this as a casual, naive, non-scientific description please, I am not a brain scientist. I am not sure if the above component-based model of the brain is still en vogue or not so much; I am pretty sure that nobody really knows for sure how the brain works mechanically in this aspect.