Yeah, I think that's what I was trying to say - the big problem with the alt history you're proposing is how do we stop the spread of Christianity and the prestige of Rome - both need to be mitigated or weakened until Islam has time to come on the scene in a big enough way.
But in the case of Rus prestige was not of Rome but of Constantinople. The Catholics lost the "competition" (which is a different subject).
Now, from the perspective of (future "Saint") Vladimir & Co choice of the Greek Orthodox Creed had certain advantages: (a) existing cultural links and probably even "Constantinople lobby" in Kiev, (b) secular power clearly having an upper hand over the Church, (c) strong trade relations and (d) not to be neglected, impressive rituals ("we thought that we are in Heaven" as one of those present at the religious service in Constantinople put it).
Would this make Islam case hopeless? I don't think so:
(a) Culturally, Rus of that time could go any way because in each of these choices there were some features well adjusted to the existing life style.
(b) Trade links with the world of Islam had been old and well established (huge amounts of Islamic coins had been found all the way to the Baltic coast).
(c) Unlike Byzantine Empire, Caliphate never was an enemy.
(d) Adoption of Islam would result in a lesser religious dependency than was OTL case with the Greek Church (it took the fall of Constantinople for the Russian Church to elect the 1st mitropolit of its own and an extra century to establish its own patriarchate. Baghdad was too far and too irrelevant militarily and politically to establish the same level of religious dependency.
(e) Alliance with Caliphate could be useful in a fight against the permanent enemy of the Kievan Rus: the nomadic tribes that lived in the Volga-Don steppes. While the Byzantines were not helpful at all against them (and sometimes were even, with a good reason, suspected in encouraging them), alliance with the Muslim states would mean that these tribes are squeezed between Rus on the North and Caliphate on the South (the Muslim states had been stretching all the way to Azerbaijan).
But the question was not as much possibility of that option (for WHAT IF a non-zero chance is enough because it does not require ASBs) but what would be the consequences of its implementation. For all practical purposes Baghdad Caliphate would be gone in the XIII century and much earlier its real power would be taken by the Seljuks (not to mention competing Caliphates and versions of Islam), leaving Rus practically free of the outside religious influence. In a long run (all other things being more or less the same), this may result in unification of the Muslim Russian lands with the Muslim Horde creating very interesting geopolitical situations. In OTL, while Tsardom of Moscow had been copying the trappings of Byzantine Empire, ideology of its absolute monarchy was developed under strong influence of the (Muslim) Golden Horde.
Relations with their Western neighbors could change. Not that they ever had been peaceful but the religious differences would became much more prominent but, realistically, in OTL "outlanders" took out of the "Russian lands" (a very vague term, which includes territories that were not even a part of Kievan Rus) pretty much everything they realistically could and only their weakening by the XVIII century changed the situation.