We know from Neil's words that the memory machine can't implant completely fabricated memories, because the mind of the patient will reject them. It can only nudge the memories along through subtle changes, such as transfering a desire from old age to childhood, or change small but fundamental aspects such as a few students dragging River away with them, or the car somehow not being run over by the car. The rest is done by the mind of the patient, which, aided by a extensive wiki, uses his or her imagination to build new memories.
My hypothesis for why the same characters and places reoccur in the reconstructed memories even when much of the rest changes is that the patient is still the very same person as before, with but a slight change to her or his personality (if any), and the memories are still there, so instead of creating new memories from scratch to remember events which already happened, the patient rather changes his or her old memories of these enemies to account for the change. After all, the only people that can be brought into new memories are those the patient remembers or which are in the public domain, everyone else will just be a grey shade.
As a piece of evidence for this, we've got the fact that River still cuts her hair in her old age, despite having no reason to any longer, because Johnny remember her cutting her hair for unknown reasons, and these reasons weren't resolved to him, so he has no reason to remember otherwise now.
Furthermore, I believe what others have said about the beta-blockers still fuzzily unlinking the earliest childhood memories to be true. Johnny still won't remember anything before the beta-blockers even after Eva saves Joey, because those memories are still purely subconscious (the machine can only nudge, not move or transplant memories), but his subconscious will remember Joey as not dead, which affects Johnny's conscious memories, and therefore Joey can follow him throughout life, while Johnny still won't remember any of their childhood.
See it this way: the memories are hidden by the beta-blockers, not by the memory of the beta-blockers, so even if Johnny's subconscious won't remember the beta-blockers any longer, the memories will still be hidden, because the beta-blockers were still there in the physical reality.