CIV4ReligionInfo.xml is the correct file to remove the religion from given the following:
1. All the objects in this game are referred to by multiple files, so if you add or remove anything you will need to go add or remove the appropriate references in other files. For a religion you will need to go to the units file and remove the reference to the religion on any unit that used it. You will need to go to the building file and remove any reference to builds that used it. Then load the game, if the game shows errors on a reference to the religion during the load note the file and go clean the reference to the religion out of that file. Repeat until all the errors are gone.
2. The Gamefont.tga and the gamefont75.tga files. I hate these files. These files are a collection of icons, among them are the religion icons. The religion icons are in order such that the first icon goes with the first religion in the Civ4ReligionInfo file, the 2nd icon goes with the 2nd religion, etc etc. The result of this is that if you remove the 3rd religion from the game then the former 4th religion (which is now 3rd in the file) will now be using the religion icon of the religion you removed, the former 5th religion will be using the icon for the former 4th religion, etc. So you have to go change the Gamefont.tga and Gamefont75.tga files to match the layout of your religions.