While your point is fair with regard to the High/Late Middle Ages, Tolkien was largely inspired by Old English and more generally Germanic epic literature (some of his articles on Beowulf still are quoted in modern scholarship), which was indeed written in the (Early) Middle Ages (for OE texts). Though all these works purported to take place in a distant heroic age (and indeed incorporated some kernels of truth about this past, the way Homer got some elements right about Mycenaean civilisation), they also reflected the social conditions and the ideals of people who wrote them. For instance (I am relying on a Tolkien wiki since I am no expert of his works), the name “Eorlingas” that he gave to the people of Rohan was a common formation in Anglo-Saxon England to designate small polities (e.g. Hæstigas, the people of Hast > modern Hastings). Names like Erkenbrand, Grima or Theodred all are credible Germanic names. Other elements were inspired by OE poetry, such as the riddles of Bilbo. The free society under a king you describe finds good equivalents in the idealised depictions of warrior bands in texts such as Beowulf, etc.

/e : that being said, your point on the shift towards a more “historical” fantasy (as opposed to the original “mythical” settings) remains entirely valid.

Fantasy really has its roots in Romanticism in art, the great artistic movement of the 19th century. You had Byron, Shelly, Wagner, HC Andersen, the Grimm Brothers, Fairy Tales, Ivanhoe, Pre-Raphaelites, the Arts and Crafts movement, etc. Neo-Medievalism is the more specific term. In a reaction to industrialization, art looked back to a distant and supposedly-glorious past, and the middle ages in particular. For the British, there was also particular interest in anything pre-Norman - Beowulf, Vikings, Arthurian legend, Tristan and Iseuit.

All over Europe, old medieval castles were rebuilt, some, like Neuschwanstein, were brand new and really pure fairy-tale and nothing like what actual medieval castles looked like.

To a large extent, the modern layperson's idea of what the Middle Ages looks like was 'invented' in the literature and art of that period - which was not always historically correct. For instance, when one thinks 'medieval castle', the image is typically one of bare stone walls. Even though actual medieval castles tended to have plastered or limewashed walls, not bare stone. But the 'medieval' aesthetic of the 19th century dictated that bare walls it was. (to the extent that in many of those restorations removed plaster on actual medieval castles to make them look more 'medieval' rather than medieval)

Another example: Interest in Vikings? 19th century. The word 'viking' hadn't even existed in English until then, and had been forgotten entirely in Scandinavian languages as well until their romantics revived it. Stereotypes like the horned helmets came about then as well.

Romanticism came to an almost complete halt after WWI, and gave way for Modernism in art. Tolkien (and friends of his like CS Lewis) was very much working in the romantic tradition, so he was significantly past his time. Which is likely a reason why the Lord of the Rings initially received a quite cool reception among literary critics. 50 years earlier and it'd more likely been hailed as an instant classic. Tolkien is not longing back to the 19th century, but to the 19th century's longing back to the middle ages. The 19th century was the age of Empire, of the steam engine and railroad, of factories and universities, of democracy and trade. The feudal society that romanticism longed back to was definitely dead by then.

Domestic American romanticism (e.g. Poe, Thoreau, Dickenson, Washington Irving) was not very medievalist, and when America did look back, it was more often to ancient Rome and Greece - America was considerably more neo-classicist than Britain and most of Europe. But British romanticism (like so many aspects of British culture) did have a huge influence on American culture. Hence, the American concept of the 'Viking' for instance is rooted in the British romanticist idea of them, as barbarians but also 'noble savages' of a sort. Scandinavian romantics loved Vikings too, but had a different view of course - skipping the 'savage' part. Germans on the other hand would rather emphasize their ancient Germanic warriors and rather talk about Wotan and Nibelungen rather than Odin and the Sturlungs.

I would point out that Gondor is, in fact, more or less feudal. During the war with Sauron, the steward summons his vassals, and they seem to owe military service in exchange for their positions.

Medieval fantasy actually dates back to medieval times.

Notably, the Arthurian legends. The poems of Chrétien de Troyes (Perceval, the Story of the Grail, Lancelot, the Knight of the Cart) in the late 12th century, and Mallory's Le Morte d'Arthur (1485).

So you had knights and kings, swords and sorcerers, castles and maidens and dragons, right from the beginning. Tolkien borrowed from it, but he didn't invent the genre, nor did he merely copy it.

edit, this was jmo, here LOTR was very much a commentary on Tolkien's contemporary England (and the rise of fascism in Europe).

edit for Dragons.

Pretty much all the important aspects of medieval life are entirely missing in Tolkien. No feudal hierarchy, no state enforced religion, not even much religiosity. There aren't even any knights. They have kings, with actual, not ceremonial powers but it seems that everybody under the kings is an equal citizen

I disagree with this point. Though Tolkien is not overly concerned with social stratification, it is definitely present throughout the work, and even more so when taken in the context of his other work, it is certainly visible. Both Merry and Pippin swear fealty to the rulers of Rohan and Gondor, respectively, to gain status as a sword-thane in service to the King, or as a member of the Tower Guard. Take a look at Pippin’s formal oath in service:

Here do I swear fealty and service to Gondor, and to the Lord and Steward of the realm, to speak and to be silent, to do and to let be, to come and to go, in need or plenty, in peace or war, in living or dying, from this hour henceforth, until my lord release me, or death take me, or world end. So say I, Peregrin son of Paladin of the Shire of the Halfling.

Nor is a culture of an elite aristocracy absent. The Princes of Dol Amroth are lords of a semi-autonomous region subject to the kingdom of Gondor. In the chapter ‘Minas Tirith’ in the Return of the King, Tolkien describes in detail the procession of lords and followers, who are arriving from the rural outlands to defend the city in its hour of need. On another note, Saruman technically owes fealty to Gondor as guardian of Orthanc.T he situation is similar in Rohan. There are frequent references to the éored, comprised of the knights of a lord’s household, and the ambience and setting of the Golden Hall in Edoras is reminiscent of Hrothgar’s Heorot in Beowulf. As others have noted, Tolkien was heavily influenced by Germanic epic literature, and that can be seen in lord-follower relationships throughout the work.

That being said, you’re right, there are a lot of other influences from different places and cultures, including Tolkien’s own memories of the English countryside of his youth. After all, the smoking of pipe-weed is a past time that would not be popular in Europe until after the discovery of tobacco in the New World. So I see your point. However, I do think the medieval, particularly early medieval heroic culture, is a strong, if not the strongest influence, in the creation of Middle-Earth