Hard to say. We know there were other missionaries running around (e.g. the church in Rome was founded independently of Paul); we even know some of their names, but we can't be sure how they differed theologically.
If Christianity retains the Jewish law (especially circumcision), then that will obviously massively affect its spread. It will still have followers outside of Judea when the Jewish Revolt happens, so it won't necessarily be wiped out, but beyond that it's hard to say.
EDIT: Mary Magdalene and Paul don't seem to have interacted at all in any of our sources. Indeed, Paul seems to have been at best tolerated by the Church in Jerusalem (the Letter to the Galatians is an excellent, although biased, account of Paul's interactions with the Church in Jerusalem at this time). Certainly there is no reason to believe he "kicked her out." Paul has an inconsistent attitude towards women, complicated by the fact that several of "his" purported letters (including the letters to Timothy and Titus, which are by far the most misogynistic) were probably written later by someone else, and other surviving letters show signs of editing.