If stories mentioning pagan gods were not tolerated you'd have to throw out a lot of sections of the Old Testament.

When it comes to Norse Mythology, there does not exist any written records by anyone who believed in the religion. Every story we know of in that case is known because those stories continued to be told by Christians for centuries after conversion. Iceland 'formally' converted in the year 1000 and was likely entirely converted by the late 11th century, but the main collection of Norse mythological stories, the Eddas, were not written down (in Iceland) until a few decades into the 1200s. People did not transmit these stories because the people were secretly pagan, but simply as entertainment and part of their culture. They even continued to compose new stories, and that was in fact the purpose of Snorri Sturluson in writing down the Eddas. He wanted to preserve the traditions of skaldic poetry. And he wrote, explicitly, that just because one wrote and told these tales, it did not mean one should believe in the divinity of these gods. Snorri engaged in euhemerism, arguing that, like the Roman gods of old (who were also fairly well-known in the Middle Ages, although as I wrote last week - not by their Greek names), they had merely been powerful men whose great reputations had been exaggerated into divinity by posterity. Linguistic distinctions were made as well, since the term for the Christian god (guð) was a distinct one from the one that'd been most commonly used for the Norse gods (ás).

There's a bit of survivor bias going on here, where people seem to assume that the stories of the Eddas were preserved because they were religiously important. It would seem more likely to be the opposite, that texts of ritual importance would not have been transmitted by Christians - and they were Christians. And it was the ritual that made the religion, not the stories. It was the rituals that were banned by the Scandinavian early medieval laws; holding blót (sacrifice) at a harg or hof or sacred grove, eating horse meat and other such practices. Story-telling is not addressed.

If you read the Eddas, you'll have heard a bunch about Odin and Thor, but you still can't say how a blót was actually performed, how to ask for intercession by the gods, what a cult site looked like and why, what the wooden posts were for, and how the amulet rings were used. Historians and archaeologists have repeatedly pored the written sources to explain the physical evidence we have of the cult, but it only gives the faintest of clues.

When it comes to actual pre-Christian ritual texts, basically the only one we have written evidence of are the Merseburg Charms. Those survived into the Christian era, but by substituting the names of pagan gods for Jesus and saints. This is probably representative; where pagan cult elements survived, it was in christianized form. So I would argue that the survival of pagan ritual and the survival of the stories were rather distinct things.

The Merseburg Charms also mention a god Sinthgunt who is unknown from the Eddas or anywhere else. The Eddas make only the briefest mention of the god Ullr, yet if place-names are any indication, there were more cult sites for him than for Odin or Thor in Sweden. Heimdallr and Loki on the other hand have no place names. (one should note that there are hundreds of old place names, named for the old gods in Scandinavia, and never any concerted effort to change them all) There is a (fairly recently found) spindle whorl that does invoke Heimdallr - but also "Þalfa" who is unknown from anywhere else. When it comes to Loki there's really no evidence of him having any cult. As prominent as he may be in the stories, being a story character may have been his main role. In any case, the point is again that the Eddas are not necessarily a very good guide to what the actual cult was.

Iceland had a strong literary culture, which lead to the recording of many sagas and the Eddas in the Middle Ages. They did not do so because they were more pagan than other Scandinavians; on the contrary, Sweden converted a full century later. Iceland had even been through a fairly puritanical period in the late 11th century and early 12th century when bishops Jón Ögmundsson and Gissur Ísleifsson, among other things, managed to get Icelanders to abandon the pagan week-day names (the only Germanic language to do so), but they were also strongly discouraging of music and dancing. In short, they were puritanical even by the standards of the day. Also note that the Icelandic Commonwealth had two bishops and diocese (Skálholt and Hólar) already then, which meant not only more bishops per-capita compared to the rest of Scandinavia, but the lack of a king also meant their bishops were even more powerful. Yet, the stories and skaldic poetry obviously survived that puritanical period.

But not just in Iceland; we have no written records but there is still evidence of Eddic motifs in art from the rest of Scandinavia in Snorri's days; even in explicitly Christian contexts. For instance, the motif of Gunnar Gjukesson in the snake pit occurs in Uvdal stave church in Norway and several baptismal fonts in Sweden. That story must have still been widely known at that time.

It's also been argued that some stories may have also been promoted or favored because they were considered to be analogues of Christian stories, such as Thor's fishing and catching of the Midgard serpent, being an analogue to the biblical Leviathan of Job.

We are also not entirely without Norse mythological stories from the rest of Scandinavia, even if the Eddas are the earliest sources. For instance the story of Þrymskviða (where Thor dresses up as a bride to get his hammer back) is known from the rest of Scandinavia, even well after the Middle Ages, many centuries after conversion.

Anyway, so your average medieval Scandinavian post-conversion would probably be telling the stories as most people do today, without believing in the divinity of the characters involved. Which doesn't mean everyone would've thought doing so was okay; Bishop Jón Ögmundsson clearly wouldn't have. But bishop Absalon of Denmark a generation later (and who himself led 'crusades' against the pagan Wends) may not have minded as much, seeing as his clerk Saxo Grammaticus wrote of Scandinavian history and mythology.

The Harry Potter books are in no small measure inspired by actual Medieval and Renaissance magic and alchemy, and the way the church(es) and clergy related to those things is diverse and complicated. Much of the folk magic was not of pagan but christian origin, in the that the beliefs originated from christian theology and ritual - but at the same time were not sanctioned by the church. For instance, believing in that you would be protected by carrying a vial of holy water. That practice obviously springs from a genuine belief in the power of this sacred substance, but from the church's point of view, the belief that the holy water had a power in-of-itself independent of its ritual/liturgical context was in error. But the broad masses were largely ignorant of those theological finer points and the difference between sanctioned rituals and unsanctioned magic was not so clear. Even the Puritans engaging in witch hunts in the 17th century were no exception from the folk-magical beliefs of the time.

It depends on when in the Middle Ages and where in Europe. Few people become Christian overnight, as true today as it was in centuries past. Let's start with what Anon says here about the Roman Empire after Constantine (who converted) and what /u/Steelcan909 says here about Norse conversion to Christianity. It's also clear from what /u/Daeres says here that many Classical texts were transcribed/translated by churchmen.

/u/itsallfolklore and others tackle a version of your question here.