The problem here is one of terminology. 'Feudalism' isn't a system of government that can be 'used' like Representative Democracy or Royal Absolutism, it's a label that we've retroactively attached to a whole network of interconnected relationships of power and mechanisms of state used largely out of circumstance, necessity and tradition.

'Feudalism' as its popularly recognised 'begins' after the collapse of the Western Roman Empire, but this isn't a new system, this is simply the various successor states falling back on the old, local - often tribal - mechanisms of government that either pre-dated Rome, or were the only things possible without the extensive infrastructure of the Roman Empire. Effective governance requires either a significant bureaucratic infrastructure, for which you need roads, schools, literacy and a series of royal or state offices and officers, or it requires the immediate presence of the king and his men. For many immediately post-Roman early medieval successor states, the area that a king could effectively control was limited to the area that he could directly reach with his army. What we now term 'feudalism' is a direct response to this scenario; a mutually-beneficial relationship between potentially rival polities that operates on both stick - "Do what I say and I won't have to come over there and invade you (which I don't really want to do incase He invades me)" - and carrot - "Cooperate with me and we'll have peace, prosperity, and mutual assurance against That Guy." At the root of these relationships are close personal relationships between a king and his subordinates, which makes expanding these relationships beyond the king's immediate borders quite hard.

You'd think that Medieval kings would try to replace their feudal lords and nobles with Bureaucrats, but you'd be wrong

Medieval monarchs absolutely do rely on bureaucracy. The literacy and organised heirarchies of the Catholic Church are integral to the expansion of so much of early medieval Europe for precisely this reason. Laws, charters, grants, letters, reports and such are absolutely fundamental to models of government, but are used to enforce what we today term 'feudal' relationships. The effective maintainance of authority is still essentially based on the effective projection of power, and bureaucracy largely serves to solidify and formalise these relationships rather than replace them. In Anglian Mercia, subordinate territories are brought into a federation of other (essentially) tribal states, while in 8th and 9th Century Wessex, kingdoms such as Kent are left essentially semi-autonomous, although increasing bureaucracy allows the reigns of power to be consolidated and solidified far more than a vague oath of submission to a Bretwalda might previously have done. To try and replace these autonomies entirely with an autocratic or purely bureaucratic power would require an investment of manpower and wealth and provoke a risk of rebellion that simply wouldn't have been feasible.

There is a vast expansion of royal bureaucratic authority in ninth century Wessex and Mercia in response to the Viking threat, and while this does institute a much broader spectrum of royal authority, officers and sites, it is incredibly expensive to undertake, and faces not inconsiderable resistance. Alfred - and by proxy his biographer Asser - have to undertake a vast PR campaign to convince the regions to back the reforms, and maintaining political control over traditionally-independent Northumbria remains a problem for English and British kings arguably until the 1500s. For much of French history, the monarchy was unable to project power outside of the Île de France, making autocratic power outside of this small area impossible.