I think you're talking to the wrong point. These memories aren't being encoded in germ cells, they are after the fact changes to DNA in mature neurons which have completely differentiated. I would think it's very possible at that stage of development for them to add or remove segments of DNA in order to encode new information not related to the development of the cell as long as it didn't interfere too much with parts that are actively used for the ongoing upkeep of cell activity. It would need to alter how the cell functions a little bit for the changes to modify the neuron's ability to process signals though.
I should note that studies have demonstrated that bacteria who have been modified not to be able to consume lactose will develop mutations that allow them to consume lactose again much more quickly than would be expected given the number of bacteria, the rate of random mutations and the size of the genome. It has been hypothesized that there is a cellular mechanism to control which portions of DNA are easily mutable, possibly through a combination of chromatin structure, epigenetic modification and changes to the local chemical environment via metabolism.
This mechanism might exist in a scaled up form in humans.
I suspect in the future we might find mechanisms beyond simple natural selection that allowed those mechanisms to get encoded in genetics.