Let's assume that the Bedein were on Earth during the Soia period half a million years ago, and remained there until relatively recently in evolutionary history. The longer they're on Earth predating humans, the more plausible the Lotai evolutionary counter becomes, and the more recently they were made extinct on Earth, the more likely any instinctual response to them would remain preserved in the survivors, to say nothing of vague cultural memories.
I've got two possible scenarios in my head.
The first is that they suffered from the Toba Catastrophe worse than the human population did ~70,000 Years ago. What few survivors there were weren't enough to rebuild their population and aggressive hunting of the remaining vulnerable human populations weeded out individuals lacking a lotai. The last of the Bedein die out on Earth, leaving the remaining 1000 - 10000 breeding pairs to repopulate.
The second is that as human civilisation began to really get off the ground 10,000 years ago, there was an effort to exterminate them by stone age populations living in and around Africa and the Mediterranean in the coastal and river/lake systems in those regions, largely succeeding with perhaps a
last gasp in the late bronze age before disappearing altogether.
Lack of evidence in both scenarios can be attributed to being aquatic, sea level rise, and perhaps a cultural more that demands that the body of a Bedein be destroyed. Since I don't imagine we'll have scoured the sea floor thoroughly in the 2160's, and fossilisation in shallow waters is I think somewhat dubious, it's plausible that there's little hard evidence of their existence on Earth.