The claim isn't that there were not relationships of service and duty based around land, but that what we understand as 'feudalism' is something we have constructed, rather than something that reflects what was actually going on.

The idea of feudalism emerged in the 16th/17th centuries based on very specific evidence from one particular area, and it is argued that this has been anachronistically extended back into the past where it did not exist in the same way, if at all. This constructed feudalism potentially leads scholars to see particular words and terms as reflecting their idea of feudal relationships, even if those words and terms did not mean the same thing at the time.

Another problem is the huge regional and chronological variations - what might have been 'feudal' relationships in 11th century Burgundy might not exist in 11th century Languedoc. For that matter, what existed in 11th century Burgundy might be different to what existed in 13th century Burgundy.

From these problems, Elizabeth A.R. Brown argued from 1974 that we should essentially reject and not use 'feudalism' given its constructed nature - that we had in fact become so trapped by the idea of feudalism we were not properly understanding what the sources and evidence were telling us.

If you're so inclined as to start digging into some historiographical debate and arguments (thanks to http://www.reddit.com/user/TheGreenReaper7 for the additional sources)
Bisson, T. N., “The ‘Feudal Revolution’,” Past & Present 142 (1994) 6-42 Bisson, ‘The ‘Feudal Revolution’: Reply’, Past & Present, n.155 (May, 1997), pp.208-225.
Bisson, The Crisis of the Twelfth Century: Power, Lordship, and the Origins of European Government, Princeton, 2009
Brown, Elizabeth A. R. “The Tyranny of a Construct: Feudalism and Historians of Medieval Europe.” The American Historical Review 79 (1974) 1063–1088.
Barthélemy, Dominique and White, Stephen D., ‘The ‘Feudal Revolution’ Past & Present 152 (1996) 196-223
Cheyette, Frederic, ‘Review of Fiefs and Vassals’, Speculum, v.71, n.4 (Oct., 1996), pp.998-1006. | Ermengard of Narbonne and the World of the Troubadours, New York, 2001. | ‘Some reflections on violence, reconciliation and the “feudal revolution”’, in Conflict in Medieval Europe, ed. P. Gorecki and W. Brown, Aldershot, 2003, 243-264. 'Some reflections' is available from his Dropbox page: (https://amherst.academia.edu/FredricCheyette).
Hyams, Paul., ‘The End of Feudalism: Review of Fiefs and Vassals’, The Journal of Interdisciplinary History, v.27, n.4 (Spring, 1997), pp. 655-662. | ‘Homage and Feudalism: A Judicious Separation’, in Die Gegenwart des Feudalismus, ed. N. Fyrde, P. Monnet and O.-G. Oexle, Göttingen, 2002, pp.13-50.
Reuter, Timothy and Wickha, Chris ‘The ‘Feudal Revolution’’, Past & Present 155 (1997) 177-195
Reynolds, Susan. Fiefs and Vassals: The Medieval Evidence Reinterpreted. (Oxford, Oxford University Press, 1994)
Strayer, Joseph R. ‘Feudalism in Western Europe’ in Feudalism in History, edited by Rushton Coulborn, (Princeton, Princeton University Press, 1956) 15–25

Three prominent British historians engaged in a debate about the knight’s fee and its role: Crouch, David, ‘From Stenton to McFarlane: Models of Society in the Twelfth and Thirteenth Century’, Transactions of the Royal Historical Society, Sixth Series, v.5 (1995), pp.179-200.
Carpenter, David, ‘The Second Century of English Feudalism’, Past & Present, n.168 (Aug., 2000), pp.30-71.
Coss, Peter, ‘From Feudalism to Bastard Feudalism’ in Die Gegenwart des Feudalismus, ed. N. Fyrde, P. Monnet and O.-G. Oexle, Göttingen, 2002, 91-99.

You are asking two very different questions.

When historians say feudalism didn't exist they are referring to the holistic analytical model called feudalism. /u/idjet sets out what that model (which ironically was so I'll-defined as to be meaningless) was here and discusses its fall from grace in the late twentieth-century here, I will chidingly say that the answer to this question was in the FAQs and you should check before posting.

Your second question (serfs answer to lords who answer to kings) is rather easily disproved off-hand by examining Occitania where land could be held in allod (ie. 'of' no one). While the Occitan aristocracy might owe 'feudal' obligations for certain territories and titles they also held lands entirely in their own right not owing services to any king for them. On the issue of serfs and peasants, if the model was as neatly cut as you wish to believe then how could a king demand the homage and fidelity of his entire populace as John of England did in 1209? Surely he would only need the homage of his aristocracy and could rely on the rest through the feudal pyramid. There were also royal dominions (demesne - although like 'fealty' that term is anachronistic; dominion and oaths of fidelity are less loaded and useful) in which peasants answered directly to the king. In no small part 'feudalism' is being discarded because it enables these kind of oversimplifications.

The medieval world was rather diverse. It doesn't fit into neat categories and systems. The chief problem with feudalism is that it is anachronistic on the one hand, and impossible to usefully define on the other. It has little merit either as a representation of what was going on in medieval society up to c.1200x1300 or for systematising that society as historians.

Edit (addition):

This was a working draft of a conference paper I wrote (now discarded because it's far too long) but it explains the role of homage and its multiple functions:

I begin with a description and explication of one of the most famous medieval rituals: homage. Homage was an act in and of itself, but the ritual was often combined with two other distinct and not wholly necessary acts. As you can see from the image here the doer, kneeling, places his clasped hands between those of the receiver, while doing this he would utter his intention to become the man (hominium) of the receiver. Then, standing, the homager would recite an oath of fidelity, while touching a holy relic or the Gospels to sanctify his oath. Finally, the doer and the receiver would kiss. These rituals are layered in nuanced meaning carefully weighed for the public that would witness them – a vital mechanism for enforcement in a non-documentary legal culture – but even when legal apparatus began to take a written form the ritual remained popular and public.

Homage was done in this manner but there were a host of performative variables which are almost invariably lost to us in the dry charter source which survive. Did the doer bow their head in submission or meet the gaze of the receiver? Did the two share a cup or dish at the feast to further demonstrate their friendship, if a feast held at all? Yet its meaning was not solely constricted to one interpretation or used for one purpose. Homage can be somewhat anachronistically systematised into four key archetypes: 1) feudo-vassalic; 2) peacemaking; 3) recognition of status or rights; and 4) lateral agreements. So what do these archetypes mean? Well, they encapsulate the entire scope of high medieval politics in the Middle Ages.

1. The first feudo-vassalic was the most famous. According to the Classical historiography of feudalism the act of homage, which was done by a vassal to a lord in exchange for a grant (dono) of land to be held in fief (in feudo) as the man of (hominum) the lord, this is not the time to fully explore the deconstruction of this model which began, in print at least, in the 1970s with E.A.R. Brown’s seminal article: ‘The Tyranny of a Construct’ and fully expounded in Susan Reynold’s opus Fiefs and Vassals: The Medieval Evidence Reconsidered. This deconstruction has forced historians to reconsider what role this still evidently important ritual played in medieval societies. This bond could be ritualistically broken by its sister act 'defiance' (diffidio). This involved another volo in this case to reject (Fr. rejeter) and a violent gesture - throwing a stick or a thread from his cloak to the ground (sometimes breaking the object before doing so. Now this is a rather uncommon ritual to find in the sources themselves, which either indicates that it was rarely done, or that it was incorporated into less official (and thereby recorded) declarations of animosity.

2. Paul Hyams proposed that homage was a flexible and pluralistic ritual highlighting that to ‘eyes unclouded by feudalism’ homage could be ‘judiciously separated’ and its centrality to peacemaking and feud settlement became apparent (even if only sparsely represented in our surviving documentation). Hyams' article ('Homage and Feudalism: A Judicious Separation', in Die Gegenwart des Feudalismus, eds N. Fyrde, P. Monnet, and O.-G. Oexle, Göttingen, 2002, 13-50) inverted the pairing of homage and defiance arguing that homage was likely used to reconcile two previously formally feuding parties (the hostilities publicly opened by the act of defiance and publicly closed by the act of homage). Clever as the theory is, there is rather little reason for the ritual defiance to have survived in our sources. However, homage was frequently employed in inter-polity peacemaking. Wales is a particularly good example of this in the twelfth- and parts of the thirteenth-century, as the Welsh did not employ homage feudo-vassalic-ly until c.1250 (internally at least).

3. John Gillingham, discussing the homages done to the French crown by the English kings, elevated the third type of homage to central importance – that the ritual was a public recognition of the rights or status of the homager. He also persuasively argued that the kings of England would rarely do homage when they were in positions of relative strength to the French – and would instead send their heirs in their stead. Thus this form is an excellent tool for discerning relative power between doer and receiver. See Gillingham, 'Doing Homage to the King of France', in Henry II: New Intrepretations, eds C. Harper-Bill and N. Vincent, Woodbrige, 2007, 63-84.

To explain this more fully. A claimant or heir might seek public affirmation of his rights or to a contested claim. One means of doing this was homage as the receiver, under most developed law codes which deal with homage, was now bound by law to warrant your claim. Warranty, in the developed sense, was essentially a legal security and guarantee. One method of securing warranty was by public homage and another was by inserting a legal warranty clause into your charter. Property warranty clauses are the origins of our own modern warranty clauses (although I don't have the space to go into that now). Of course, these legal types required both parties to submit to the same law and required someone who could adjudicate over them. In medieval politics homage could be done by a foreigner to another individual in return for his support of their claim. This was what happened in Wales (well, actually the homages occurred at Poitiers) on 3-4 December 1199 when three claimants to individual three Welsh kingdoms (Deheubarth, Powys, and Gwynedd) did homage to King John shortly after his ascension to the throne. These were not legally binding agreements but instead public affirmations of support and, in essence, a promise not to support any other claimant. John reneged on at least one of the homages allowing William Marshal (who was listed as a witness on the enrolment of the charter) drive out Maelgwn ap Rhys of Deheubarth (apparently with John's tacit blessing). However, the use of feudal language in the documents which may well have been the first time a homage was put down in written record was to form (alongside another agreement from 1201 with Llywelyn ap Iorwerth) the basis of increasing English overlordship in Wales in the thirteenth-century.

4. The fourth form, that of lateral alliance or agreement has the least developed historiography, in part because it is so difficult to disentangle the hierarchical language of our surviving documents from the elements of equality that are evident in the agreements themselves. There are examples from Iberia of kings doing homage to one another to seal pacts, and it seems that confederating agreements were a common form of this. I can't really go into much more on this (as my Welsh examples aren't really applicable in a 'feudal' context, except that they started using homage as an additional bond in their confederation agreements in the thirteenth-century). A good work to begin with would be Adam Kosto, Making Agreements in Medeival Catalonia: Power, Order, and the Written Word, 1000-1200, Cambridge, 2001.

These clean-cut categories are anachronistic because they are permeable: an individual homage could be done as a demonstration of submission but also indicate the creation of a feudo-vassalic bond. Or what might appear to be a feudo-vassalic due to the technical legal language of a charter might, in fact, be a public affirmation of rights to a claim, maintaining elements of hierarchy and elements of equality.