The way I see it, Christianity and Islam both suffered different problems.
Islam's problem was a precipitous drop in its perceived moral authority early on due to the horrific infighting. This, combined with the fact that Kaliphate had made a whole lot of enemies both inside and outside its territory, meant that the Muslims couldn't follow up on their initial successes, and so the Near Eastern polytheists pretty much eroded most of their gains. Which explains why, nowadays, you're far more likely to find devotees to Horus, Dagon, Yahweh, Baal, Enlil, or even Hubal than Allah in most of the Middle East. It also explains why so many Muslims abandoned the idea that Allah was the only deity.
Christianity's problem, on the other hand, was a lack of appeal among the peoples of the area. Even in Judea, its reception wasn't particularly positive despite a seemingly promising start. Might Christianity have found a more receptive audience elsewhere?
EDIT: Sorry, I accidentally hit post before I was finished typing.