Yes, they are determined independently.
If you have "new random seed on reload" checked in options and you put 3-4 missionaries in a city with multiple existing religions, you'll be able to see it happen. Also, if you do not have "new random seed" checked, you'll be able to see something interesting as well. I'll explain with an example.
I start a game with "new random seed on reload" not checked. During the game, I put 3 missionaries in a city that has 3 existing religions. When I try to spread the religion, I get...
first: fail
second: fail
third: success!
If I reload the game from just before the missionary attempts, I'll see the exact same fail/fail/success sequence that I saw the first time. If I reload a dozen times, I'll continue to see the same fail/fail/success sequence.
Now, if I reload one more time and I initiate a combat somewhere on the map before trying to spread the religion, I'll see completely different and new results for my missionaries. Maybe the first one will succeed, maybe the second will. Maybe none of them will. Who knows? Combats generate lots of random numbers, so it "uses up" the numbers that would have gone to the missionaries. Please note that this does not "defeat" the no-new-random-seed process entirely because repeating the exact sequence of activities will result in the exact same outcome. You're just working around the process by "using up" the random numbers from the pregenerated list if you have a particular need for a "good" number from the list.
Also, I'm not advocating that people do this. If you want to do something like this, you're better off just checking "new random seed on reload" instead of using this "workaround". I'm just putting this here to show that Civ IV does, indeed, calculate each of these missionary events independently.