Yeah, so the way I see it, if you want to keep Islam from spreading once it's been preached already, you have to keep it from uniting Arabia under one banner. Once the Caliphate had done that, the clock already started ticking for Heraclius and Yazdegerd. Even though I like to talk up my boy Khalid ibn al Walid (somebody has to!), the fact of the matter is that Abu Ubaidah, Az-Zubeyr, Amr ibn al As, and co. would probably have gotten the job done as well. Definitely with more Muslim losses, likely not everywhere that they grabbed in OTL, but I don't think offing Khalid would be enough to stop it altogether.
There's a number of changes that could be made to keep Islam from ascending in the Peninsula. Prophet Muhammad almost dies a bunch of times: the Quraysh make a plan to assassinate him the night he leaves for Hijrah that's foiled by a teenage Ali, Khalid ibn al Walid and Amr ibn al As almost geek him at Uhud when they were playing for the Makkan side, he almost gets beheaded by some dude on a horse at the Battle of Khandaq until Zaid ibn Thabit kills him with a spear on a reflex, another Makkan tried to assassinate him by shooting a poisoned arrow at him and hit another Makkan instead, Ayesha accidentally stops an assassnation attempt when she fed the cats outside some poisoned food meant for Muhammad (who gave it to her because he wasn't hungry, but she didn't like camel meat.) One guy literally tried to drop a giant rock on his head. Prophet Muhammad is basically the Fidel Castro of the seventh century as far as dodging attempts to murder him. You could have any number of these increasingly Warner Brothers-esque plans succeed.
The later Muhammad dies, though, the more I think that Islam will remain an independent force in Arabia (like a version of the hanif movement with more social force.) Even if it doesn't unite Arabia, I don't see it going away. It was too popular with the poor/socially disadvantaged for that. It would be quite different from Caliphal Islam, though, to say the least.