I've heard numerous times that the only reason polytheism largely died out was because it wasn't aggressive enough in conversion and the monotheist nations were stronger. If I had a powerful pagan nation who had a supposed prophet or demigod that claimes that the pantheon is now at war with the other pantheons and/or the monotheist unbelievers, would that give the nation and its religious peers more survivability?
I suspect the various leaders would be reluctant to go to war at the claims of a single person, but if they were a respected warrior or chief or some such maybe they'd listen. Then the problem of going to war at the whims of a god, though it IS a god...
What do the all knowing men and women of the forums think?
Based on my understanding of it the conversion of Europe happened for two reasons:
1) The Roman state cult by the 2nd century was becoming increasingly corrupt, insular, and out of touch with the masses. This led to an explosion of mystery cults across the empire, several of which were as big if not bigger than Christianity with the Cult of Isis and the Cult of Mithras as two famous examples. The death blow was the cessation of state funding and support for the Roman state cult which instead went to Christian churches and schools.
2) The conversion of the post-Roman world of the empire carved up by Germanic warlords was much less a question of grassroots appeal and more to do with power and politics. Christianity offered educated clerics who were knowledgeable in the administration of the Roman Empire, the maintenance of records, and the status that came with having something associated with the old Empire. This plus new policies by Charlemagne of forcing the tribal states of central Europe to convert or be exterminated helped push it forward followed up by an incredibly bloody process to bring Scandinavia and the Baltic in line.
In the end the spread of Christianity had less to do with deficiencies in polytheistic belief structure and was more thanks to the decisions of very powerful people. The one exception was the Roman state cult which had long been in decline by the reign of Constantine. That said there's nothing that says the Cult of Isis or another popular mystery cult could gain the upper hand if Constantine is removed from the picture. Christianity didn't really take off as a massively popular religion until after the Edict of Milan; prior to that it was very much one of MANY religious sects in the empire.