A distinction needs to be made here (and it’s a distinction I failed to make in my earlier post) between the spread of Christianity before it became the official state religion and after. Christianity originally (before it became officially adopted by the state) spread throughout the Roman empire, and not far outside it, due, in large part, it looks like, to the internal transportation and communication networks within the Empire. You were nominally under the same government, with an established road network, from Spain to Armenia, from Egypt to Britian. It’s the same reason early Christianity was strongest around the Mediteranean…Mare Nostrum was the center of transportation and commerce within the Empire. Why it succeeded in becoming the religion of the Empire is dealt with by Cecil in his column, and I won’t add to that, except to say that, if you’re in a place with a lot of political and social unrest, you’re scared about your future, and most of the religious groups are exclusive (Worshipers of Isis were largely female, worshipers of Mithras were largely soldiers, etc.), a religion that 1. Is open to everyone, 2. Is eschatalogical and apocalyptic, with future rewards for believers, and 3. Doesn’t impose much in the way of ritual or complicated moral codes on believers, is going to be popular. After Christianity was adopted, it became an instrument of state power. To say, though, Christianity had a 600 year “head start” is true, but, within that six hundred year period, Christianity managed to convert the Roman Empire and Ireland, and was moving north into the Russian steppes…so it’s not like the religion sat on it’s hands.
Living now, with access to airplanes, CNN, and the Internet, we’ve become spoiled in terms of information exchange. Messages that would have taken years to convey 2000 years ago get transmitted in seconds now. For an early Christian missionary to travel to and try to win converts in Persia would have required several months travel to an enemy nation, where he would have been looked on with suspicion because of his nation of birth, trying to convert people from a religion (Zoroasterism) which was supported by the state, and in which, apostasy was severely punished. After the conversion of the Roman Empire, such an attempt was made even more difficult by affairs of state.
As to why Islam succeded in places like Syria, Egypt, etc (all those parts of the Empire that once was Christian), the conquering Muslim states put a great deal of pressure on the conversions of the conquered. If you weren’t Muslim, you were the victim of state sponsored discrimination, which is a pretty big incentive to convert. They were, in the words of an Azeri friend, “Sword-Muslims”. The same also explains India. As for Indonesia, it was a combination of strength of arguments, economic and military support of Muslim and pro-Muslim leaders, and in some cases, direct invasion…basically, the same thing Christianity did in Europe.