Wiki says "Caliph" means "successor", so perhaps these Christian Caliphs could be the successor of some unusually successful Christian Arab army? Perhaps, in some Islam-free environment, a Ghassanid king who "goes rogue" against the Romans who are weakened after the 602-628 war is able to conquer much of Syria and Palestine, with his heirs styling themselves as the "successor" of that Ghassanid. Once they wrest Egypt away from Roman hands (or maybe conquer it from a more-or-less independent Coptic regime?) the status of the Mediterranean's most powerful state belongs to the Christian Arabs.
To consolidate, have the Romans be able to hold on to Anatolia and Constantinople as IOTL, so there's no temptation for the Christian Caliphs simply to start calling themselves Roman Emperors.