They got conquered or at least invaded by another 'normal' human group and there was a lot of rape, so there are lots of unwilling mixed race births, too many for them to expel.
Or they enslaved a 'normal' human group and slave owners and their slaves reproduced. Perhaps they faced a severe labor shortage or loss in a war, so they were forced to take slaves despite their xenophobia.
A religious epiphany that at least temporarily allowed mixed race mating. Can spin that any way you wish.
I'll add an example. Cortes, when he landed in America, benefitted from a local prophecy about white skinned peoples (http://www.bbc.co.uk/history/historic_figures/cortes_hernan.shtml) so something similar could apply to a specific group of "normal" humans who encounter this xenophobic tribe. They would essentially be exploiting a loophole in their xenophobia and purity teachings.
Another possibility is that "pure" natives are biologically dependent on something found only on their island, mountain, wherever they live. Kinda like how Jurassic Park dinosaurs were dependent on lycine being added to their diet, something similar could occur with this tribe, so pure blooded natives CAN'T survive away from their homeland. If it was autosomal recessive a mixed blood child wouldn't suffer from it, though THEIR kids might, so they must continually breed a pure blood with another race in order to be sure the offspring can leave. So, in order to sustain trade, they must create a mixed blood caste that CAN survive away from the tribe. Perhaps there is a resource they desperately want and can't make locally. They are xenophobic so they don't trust outside traders, so they need a caste of peoples who can both leave the tribe and still be considered "tribesmen" to some extent in order to facilitate trade.