The historical prominence of the slave trade in both the Christian and Islamic worlds should make it quite clear that it was hardly "unthinkable" but instead very rationalizable.
Rigid systems of social power hierarchy and oppression based on ancestry, perceived race, and occupation (which is a lot of what the worst part of caste is) were very much features of Christian and Islamic societies, even if their religions didn't codify them.