It's relative. In this case, "isolation" means "around Scandinavia", and would still include contact with homo sapiens (thus the stories). If there were out-competed everywhere else by Homo Sapiens, but found a niche in that area, due to some geographic or cultural difference, then they may have survived for some time. In fact, it may have just been the lack of competition with Homo Sapiens until fairly recently in those areas (H. Sapiens apparently late to colonize Scandinavia and neighbors[1][2]. Iceland, in particular, didn't see a colonization of H.Sapiens until the 10th century.

Occasional contact with Neanderthals by the people that would eventually move into Northern Europe, and possibly also the lack of anywhere for Neanderthals to retreat to, leading to more conflict, may have exacerbated the "otherness" with which they were seen (a natural extension of conflict/war), and solidified them under a different name for those peoples, which was then passed down through oral tradition.

I'm not saying any of this is likely, just that I'm not aware of anything that makes it entirely implausible (but I'm by no means an expert in the area). It's an interesting "what if".

1: https://en.wikipedia.org/wiki/Historical_migration

2: https://en.wikipedia.org/wiki/List_of_countries_and_islands_...

Apparently the caves of Gibraltar show Neanderthal occupation 25K years after all others died out in Europe. It can happen!