Dealing with religion in alternate history is always dicey. And when it gets treated around here at all, it's usually on strictly materialist terms - i.e., religious entity as purely man-made phenomenon.
As a Catholic, I do believe that the church is 1.2 billion and change *for a reason.* But having said that...
1. On purely materialist terms, I think your best bet by far is a very early POD.
Probably with the Gnostic crisis of the 2nd century. The potential there would be that Christianity devolves into competing mystical cults. I think that was very unlikely just on the terms of who the Gnostic leaders were, and how compelling their theology actually was. But this was clearly a point when the Church was at its most vulnerable, still trying to flesh out its own ecclesiology, liturgy, and soteriology.
2. After that, it has a great deal of momentum going, and only a powerful external threat with an equivalent level of metaphysical confidence will suffice. And that can only point to Islam. Best bet there would be Christian defeats at both Tours (732) and the Siege of Constantinople (718).