Most tooth loss is caused by bacteria that lots of people are immune or resistant to, not diet. It's something that people don't talk about much; I'm immune to cavities, and wouldn't know that such a thing were possible if I wasn't, and dentists hadn't told me. It's not uncommon around the world, but I think it's generally recessive. Large groups of native Americans were immune to cavities, a lot of Melanesian and Polynesian groups, and if you say that native Australians were, you'd expect to see it in southern India.

Again - I eat piles of processed sugar, I'm middle-aged, I've never had a cavity, and I've been told that without extreme neglect, I never will.

IIRC, it's difficult to develop a vaccine for cavities because it would also cause the immune system to attack certain sorts of tissue around the heart and vascular system. Neanderthals may have just tended to a different biochemistry that allowed them to develop natural immunity.