I would have to dramatically scale back my ideas to the mere survival of any of the various flavors of pagan (another nigh impossible task) outlasting the end of the middle ages.
Wait : there's a difference between Paganism defeating Christianity in Europe, and impossibility of any traditional religion to survive and lives on to, say, the XVIth century.
You could delay things long enough to have more of IOTL Lithuanian situation, including parts of Scandinavia. The pressure is going to be huge, and that wouldn't be the most likely outcome but you could have a paganism living on long enough to be transmitted up to more tolerent and secular political backgrounds within limits of plausibility.
For this i deeply apologize for wasting the time of all of the people whom were speculating about Christianity failing to convert the Romans (even though this is probably, ironically enough, the best way for monotheism to be kept out of Europe.)
You don't have to apoligize when you managed to make an interesting threads with people discussing politely on interesting topics.
Is there anyway after the fall of the WRE (476 AD) for Christianity to fail in Europe? Or to lose its dominant position?
I don't think it would be possible at this moment : Romans and romanized Barbarians where structurally christianized at this moment (Christianism, since the early IVth century, being synonymous of romanisation due to its imperial official support). You could delay things (see above) but I don't know if it would counts as "fail in Europe".
A POD I suggested was that exposure to christianity could have led to germanic priests organising their religion in a similar way. Contacts with Rome would have been sufficient to see the benefits of such an approach (and a wealth of pagan philosophy), and given the similarities in the religions of the Germans there is a chance it could spread between tribes.
I think you overlook some things.
The contacts between Romans and Barbarians were really important after the IInd century. Trade, deportees, refugees, clients...You really had an exchanged that confined to mutual acculturation, rather than "enough important contacts". By the Late Empire, you can talk about a symbiotic relationship without too much exaggeration.
Rome had the bigger deal there, mostly because of its demographical and political structures, when Germanic kingship was less hegemonic (and really became so after their entry in Romania, when rulers were identified as rex and with a decisive military role, instead of the more or less priestly kingship of the Ist).
The diplomatic pressure shouldn't be diminished : Christianity, as an imperial political tool, was to be used.
It's not going to be stressed enough : structurally, Barbarians are as much a Roman creation than a Barbarian one; and the political-religious influence of Rome had a part on it.
You may have skipped something important as well (while it may have been implicit) : Germanic priesthood is often tied up with kingship, but this kingship didn't always made it after the IIIrd century. Not only you had kings of the Goths that may have been "only" opposer to another one (as the struggle between Athanaric and Fritigern) where the Christianised rulers would have a favoured relationship with Rome.
For all we know, it's possible that non-Christian rulers did tried to stress a structuration of the rites (it seems that it was attempted with some Scandinavians), but not only they would have encountered the opposition of both traditionalists (opposed to a really powerful kingship, that would be too close of Romans and Christianism structuration for their likes) and Christians (opposed for pretty obvious reasons); but once they'd have entered in Romania, it would have been toasted : integration within and on Roman structures depended too heavily of their Christianisation.
If the Franks et al had decided that the christians were weak zombie worshippers whose god had given his believers defeat.
That's, IMO, a caricature of Roman and Barbarians relations in the Late Empire. Barbarians were all about Rome, and the imperial structures (including religion) were something they tried quite heavily to preserve, even when not of their kind of Christianism, in order to mimetic the roman imperialship. (It's particularly obvious with Theodoric).
I know that in otl the Franks Goths etc decided to convert and just take over the pre-existing power structures.
Not really. They converted, except the Franks, for integrating existing structures, for being influenced by Roman prestige (It's not because some countries use American democratic features that they submit politically to it).
Separating religion from all the other features is IMO a big mistake. Heck, Christianisation of the Goths happened before they entered in Romania.
Frankish example is a bit particular, but point out why it was needed. Because they remained pagans, the Gallo-Roman clergy had big hopes to see them fight Homeans, and made an intense siege around him. If they decided to simply tell them to fuck off, you can bet the support would have switched easily from him to another one (possibly Goths, if Alaric II went trough his religious "program").
Again, Christianisation is just another part of the whole romanisation (and imperialisation) process for the Late Empire.
It will be from this sect that any ATL Islam will draw its influence.
From what I gathered, it's often tought (without decisive proof) that non-Pauline and Judeo-Messianic influences did have a role IOTL on Islam (with non-Chalcedonian churches on a general way, much than anti-trinitarism that existed, but really develloped itself during the conquest, after Muhammad. Which makes me think that a "confusionist" instead of "associationism" accusation could appear.
Of course, admitting Islam (or an Arabic Abrahamic religion) still exists with a IIIrd PoD.
I am assuming that Homeism developed after hardline Arianism did
It appeared roughly at the same time, and both sides were present at the Council of Nicea.
I think that Homeism might have appealed to a wider group than simply those who might have been considered Barbarians
Well certainly, as it it appeared in imperial circles for a moment, as an attempt to deal with extremists of both trinitarians and anti-trinitarians and to gather the imperial-christian flock. (a bit like monothelism in the VIIth century).
That Arianism and Homeism apparead in Romania points out you had believers there, after all.
But you have some factors explaining why it was associated with Barbarians
1) The refined discussion about the nature of Christ must have went straight over the head of many followers, especially the ones from popular classes.
Doesn't mean they didn't identified with one or another side, but maybe more for reason of affinities of religious policies rather than theological.
2) And when the emperors eventually said "Nope. Full Nicean" and that non-Nicean priests and teaching went "illegal" (remember that Christianism at this point as an imperial cult, constitutive of Roman identity or at least a structure that shouldn't be opposed without nasty consequences).
3)Political identity of Barbarians, especially after their entry in Romania, was really a good part of their whole identity. Giving the incestuous relationship between religion and power, when Barbarian and Roman identities (regardless of their mutual acculturation, or maybe because of it) were to be clearly defined, Homeism looked like a convenient distinctive marker for many people (at the point that Burgundians, originally Niceans, converted to Homeism).
It doesn't mean that all Barbarians where Homeans : we know that there was pagans, Homeans, Niceans, even Jews among the Vth century Franks. But what determinated the dominance was eventually the king's stance (itself based on geopolitical realities).
Alternativly, it doesn't mean all Romans were Niceans by the Vth century, but sources are more limited there, and giving the constitutive identitary part of Nicean, it had a clear dominance.
so I am guessing that maybe to Roman citizens in rural areas, Homeism allowed them to keep links to the existing power structures that were fluctuating at the time.
Rural Romans, except in the eastern part (but that's not really relevant when talking about Barbarians), practiced sort of syncretism between their own rites and a Christianity dominant in the cities (that were the backbone of Late Antiquity administration).
As I wanted to point above : the big part of the population probably didn't that much cared about theological in-depth nuances and if making a comparison with medieval heresies is fitting, it wasn't because you were Catholic that you didn't promoted heterodoxial ideas.
Similarly to the XIIIth, the monastic wave of the VIth/VIIth centuries established a rural orthodoxy network. But I wonder how much it was a thing before.