Might it, in fact, be easier to do the other way round?
This was an era when nomadic peoples - Goths, Huns Avars, Bulgars etc) were on the move all over the place. There's no reason why the Arabs wouldn't join them at some stage, indeed it would be surprising if they didn't. OTOH, none of the others was unified by a particular religion, so it's not obvious that the Arabs needed to be. Kill off Mohammad, and maybe it's Pagan, Christian, Jewish or Zoroastrian Arabs (or some mixture of all four) who do the invading.
The problem is that the OP specified that Islam must still exist, so the classic 'No Mohammed' scenario doesn't cut it. Me, I think DValdron has a point, that the Eastern Roman & Persian empires of the time were pretty ramshackle and overextended affairs. Well, I know at least the Eastern Roman was, constantly fighting wars that left its government just short of bankruptcy while plague depopulated the cities and decreasing soil fertility in some of the old breadbaskets depopulated the countryside. And if the Romans had that much of a problem and were still able to keep the Persians at bay, then they must have been in equally shitty circumstances. He's also right about Islam being a damn easy religion to proselytize for; unlike the other great missionary faiths, Christianity & Buddhism, Islam features a very compact and easily explainable central theology in the 5 pillars. Christianity's basic theology varies wildly from one sect (and even one century!) to the next; Buddhism basic theology, though simple, requires a good bit of intellectual prowess to grasp; but pretty much all Muslims, from lunatic fringe Jihadis to contemplative Sufi mystics to modernistic engineers, can pretty much agree on the basic principles of their religion. And I know of no particularly syncretist Muslim heresies, in the way that Voodoo/Santera/Gnosticism took off from Christianity, and some of the weirder Central Asian Mahayana sects took off from Buddhism. So, yea, Islam is a very well-engineered faith, from the point of view of spreading itself.
Still, the massive rise of Islam in the 7th century OTL is pretty awesomely ASB, one of the real defining events of world history. It seems pretty plausible to imagine it petering out somewhere along the way. Now, assuming for now that Mohammed's successors were going to knock the piss out of the Byzantine Romans & Sassanid Persians, they still took a lot of territory that wasn't really controlled by those states. Its easy to imagine them failing to take North Africa or Iberia, for example, though I don't know enough about those campaigns to give any definite POD. In the East, though, I know that the central Asian, east Persian & Bactrian kingdoms & tribes resisted for a century or more after the conquest of Sassanid Persia proper. In fact, their eventual defeat was in large part because of the simultaneous rise of T'ang China squeezed them hard in the middle between the two great powers. But it would have been entirely possible, during the unstable first century of Muslim rule, before the Chinese really started pushing into central Asia again, for one of these kingdoms to come in and take Persia for themselves. Perhaps this could even lead to a Buddhist Iran...