You mentioned: “The Buddha said that the Dhamma is something completely unknown to anyone at that time. But people at that time had seen the suffering in the re-birth process…”
That’s exactly my sentiment. Ancient yogis before the Buddha were already trying to rid themselves from the rebirth process. So, it cannot be a new concept to them. Without coming across the Buddha Dhamma, one can never come to the realisation that the things we do to gratify this illusive self is indeed the opening of the pandora’s box to incessant suffering. We would never have figured out on our own the way to end this madness is actually counter-intuitive to our defiled primal nature. Even the highest external sect yogi who still has a modicum of notion – “I can. Therefore I am.” is not spared from going round in sansara.