The POD is that Islam is not founded. Byzantine Empire recovers from the Byzantine–Sasanian War of 602–628. The Heraclian dynasty consolidates the empire. The Army is rebuilt to the strength it had under Justinian. Italy is soon reconquered.
Yet the Sasanian Empire is still in the damage from the Sasanian civil war of 628–632 in which the Sasanian dynasty lost control over it's aristocracy. The Byzantine Empire conquers Sasanian Mesopotamia and it's Emperor is recognized as the King of Kings of Iran despite holding no territory there
How will this effect Christianity and Zoroastrianism ?
How will this effect European and Middle Eastern history ?
Honestly, even without the Islamic invasions it's unlikely that the Empire recovers Italy particularly quickly. Remember, there will be reappearances of the Plague of Justinian up until the mid-8th century.
And of course
we know that the Empire is unlikely to have to deal with a threat from Persia, but the Romans can't be certain of that, so they will see the need to keep substantial troops in the East to ensure peace with the Persians.
And also, the priority of Constantinople will be towards re-securing the Balkans.
At best you might see an attempt to secure Southern Italy, but that's about it.
And then at the end of the 7th century you'll have to deal with the arrival of the Bulgars in the Balkans that will cause more problems
Overall, it's important to remember that the last Roman-Persian War and the Civil War between Phocas and Heraclius wasn't the start of the Empire's problems, it was just the straw that broke the camel's back. The Empire was severely overstretched even before that and pushing the Empire's borders near to the heights seen under Justinian would be difficult and not really something the Empire should be doing. The 7th and 8th centuries should be about the Empire consolidating what they have and dealing with their internal problems.
Thing is, if the war between the Sassanids and Romans still took place, I still think the Arabs will invade, Islam or no Islam.
I'm not entirely sure about this. Islam brought a level of unity to the Arabs that had never existed prior. Without Islam there's no major Arab Army to invade the Levant with.
Not that I don't think the Arabs won't feature at all during the 7th and 8th centuries, but it just won't feature as a major military invasion. It'd be more like the Germanic migrations into the Western Empire during the 3rd-5th centuries, except that, without something like the Huns to kick them into high gear, this Arab migration would be a much more laid back and gradual process, thus giving the Romans a better chance to integrate the Arabs into the Empire. Not that the Romans can't still fuck it up (the Romans have proved they were always capable of snatching failure from the jaws of success), but it won't be an immediate loss of the East, like in OTL.
Indeed, I think the Romans will welcome the Arabs in order to repopulate their eastern provinces from the plague, heck, they might even bring some Arabs into the Balkans.