We also lived in caves for several tens of millenia across multiple stretches of time, without written language. There may have been some sort of ephemeral symbolic transfer (knots, beads, wood carvings,) but it looks like those cultures used primarily oral traditions. We know many non literate cultures develop memory palace techniques, so rigorous oral traditions can be incredibly durable and stable, with lots of information passed down accurately. All that to say, human tribes could have had detailed and specific knowledge of interactions with Neanderthals over millenia, and developed peaceful tradition that maximizes cooperation, or at least borders that kept conflict minimized. Neanderthals could likely do the same memory tricks.
5000 years is a blip - if humans find a sufficiently habitable environment, we apparently can settle for a pretty low quality of life.
It only works until it doesn't, though. Neanderthals or humans could have initiated an incident, in which traditions were distrusted or discarded or lost on either side, resulting in hostility, or they lost their elders to disease and the knowledge to survive.
Just like megafauna extinction, "bad humans were bad" probably doesn't come close to what actually happened.
Neanderthals were likely as or more intelligent than humans, implying susceptibility to all the same conflicts, biased thinking, and bad incentives that affect human cultures. It could be environmental or biological or a pure fluke that Neanderthals didn't outlive humans, but whatever the reason they're gone, it's going to be just as convoluted and nuanced as the rise and fall of millenia old human cultures.