Medieval people were more optimistic: they believed that Paradise existed on Earth in their present times in some far away land, and trusted that some travelers indeed have seen it with their own eyes. Ancient manuscripts have maps, the Paradise was located somewhere in Armenia, China, India, later in Japan: in general it was very far in the East. The Tree of Life was there, wonderful climate, of course vegetation was fabulous and abundant, with plenty of fruit to eat. There was not even a glimpse of darkness, day time always, never falling of a night, and the Paradise was filled with light seven times brighter than the daylight on the rest of the planet. The multitude of precious stones of many kinds was joy for the eyes. Abraham and Jesus was there too. This illuminated page from shows Christ on the lap of Abraham, with personifications of fours rivers in the circles of four corners of the mandorla. Those rivers are Euphrates, Gihon, Pison and Hiddekel were the four great rivers of the Paradise.
The Three of Life was in the center, also a Fountain of Life, which cured all imperfections a human body could have. Sabine Baring-Gould wrote about this myth ( Curious Myths of the Middle Ages), mentioned maps pointing the location of the Paradise, but also writes about the manuscripts in which the legend is recorded as a true fact, also he lists the various authors of the narration. For example he states that St Brendan took the journey to Paradise because one monk traveled there, and told about the wonder for this place, and St Brendan became very curious. St Brendan went to the East, very far, and reported on the Paradise he visited, and told about going further until he came to the place no one alive was allowed to cross. According to Sabine-Baring a map in the Cambridge collection depicted the Paradise as a round island located close to the mouth of Ganges. According to another legend Alexander the Great was eager to see this land of delights, but hadn't possessed proper mind, as it was an inner Paradise, not the physical one. But the most detailed account was given in the Icelandic narration of Eirkes Saga Vidforla, form XIV c. mixing pagan and Christian beliefs. The following centuries the Paradise narrations didn't die completely out, the occurred as "learned treatises."
What I was not aware of is the fact that the legend was also given strong theological validity, and is found often in the books of sermons. Books of sermons in general are quite numerous, and give a good insight into medieval religiosity, they also repeat legends. The master dissertation by Gavin S. Fort gives examples how this legend was functioning in religious life, specially interesting is the relation of this legend to medieval monasticism. Monasteries were supposed to be images of Paradise on Earth, were people had the great opportunity to cleanse their souls ans enter the state of perfection, and have angelic habits. In monastic life celibacy was equated with the attempt to live like angels, than celibacy was a requirement in monastic life, later the argument for angelic life became a point in deciding that the celibacy should be extended to priests also. Later the belief in a geographical location of the Paradise developed into the abstract meditative practice on the inner Paradise. Are you interested in additional reading? I recommend the Master degree thesis by Gavin S. Fort about Paradisal language in Medieval reform
Take a look at this mysterious diagram of a mystical Paradise from the Rare Manuscripts Collection of Walters Museum of Art, by Conrad of Hirsau, XIII c.
I didn't find the remnants of this legend in today's Europe, not a full narrative but just some short mention about which I am not sure if this is truly oral tradition as told, but this fragment is similar what wrote Baring-Gould. According to this mention the Paradise was sealed by the walls of fire, and is guarded by an angel and no one could step in. The walls of fire are relating to some medieval reports about inaccessibility, (Baring-Gould), the angel with sword is of course the cherubim of the Genesis.
