According to C. Wickham's The Inheritance of Rome: Illuminating the Dark Ages 400-1000, pages 102-104, in 5th century rulers abandoned Roman tax-paid army in favor of medieval feudal one, which was far worse. They needed the latter to settle their adherents, but why they did not use both or revive the former a century or two later? It looks as if it would give them a great advantage.
Beginning in the fifth century, there was a steady trend away from supporting armies by public taxation and towards supporting them by the rents deriving from private landowning, which was essentially the product of this desire for land of conquering élites...
But if the army was landed, the major item of expense in the Roman budget had gone... Tax is always unpopular, and takes work to exact; if it is not essential, this work tends to be neglected... Tax was, that is to say, no longer the basis of the state. For kings as well as armies, landowning was the major source of wealth from now on...
This was a crucial change. Tax-raising states are much richer than most land-based ones, for property taxes are generally collected from very many more people than pay rent to a ruler from his public land... And tax-raising states have a far greater overall control over their territories, partly because of the constant presence of tax-assessors and collectors, partly because state dependants (both officials and soldiers) are salaried. Rulers can stop paying salaries, and have greater control over their personnel as a result. But if armies are based on landowning, they are harder to control. Generals may be disloyal unless they are given more land, which reduces the amount of land the ruler has; and, if they are disloyal, they keep control of their land unless they are expelled by force, often a difficult task.
Update (answer to Mark C. Wallace's comment): The taxes were always unpopular, which did not make Romans to change their army. Once someone with a private army conquered a piece of land, it would be natural for him not to pay the adherents from taxes, but to give them land, as it would satisfy them more; but it is strange to abandon the tax-paid army completely, because it is a big disadvantage even in the not too distant future. To consider it from the evolutional point of view, the states without tax-paid army should not survive natural selection.
Update 2 (detalization motivated by Twelfth's answer from different viewpoint). As I understand from Wickham's books, in 5th century the Western Roman Empire, with its regular paid army, disintergrated into a number of kingdoms (a couple of centuries later they became Francia, Spain, Lombardy...) based on militarized landed aristocracy. Not that it was overwhelmed by hordes of 'barbarians', who invaded or were allowed to entry, but rather that its parts changed allegiance from Rome to local rulers and switched to their ethnicity.
Roman legions for centuries were not only struggling with external enemies, but also fighting each other in civil wars, because they were paid by their generals, settled as veterans by them, and thus loyal primary to them. Generals could easily seize tax-collection and start warring with each other, but still generally looked for Rome, therefore the Empire disintegrated and integrated many times.
The situation changed in 5th century. Firstly, large parts of Roman army began to consist of 'barbarians', people coming from the border regions, either inside or outside the Empire (cultural difference was not very large after four centuries of more-or-less stable border). Even magistri militum, supreme commanders, were 'barbarians', like half-Vandal Stilicho.
Secondly, the economy of Empire was declining and localizing, therefore people became to look more to their neighbors, then to Rome. It seems natural to me if both reasons reinforce each other, but Wickham is rather vague about it.
Now, it was natural for separatist barbarian generals to base their power on ethnicity, and to their supporters to consider themselves of the same enthnicity (it was not difficult as many came from Danube border, the melting pot of nations). Thus they were transformed from revolted parts of the regular army to 'barbarian hordes', which can be settled on the land and later fight for their leaders because of their newly-obtained ethnic unity.
This description seems generally coherent, but for one thing: land-settled army made states much weaker in both economical and military sense. It can be seen on the example of the successes of Byzantine Empire fighting with many 'barbarian' kingdoms. So it seems to me that if, say, Franks saved the vestiges of tax system and returned to the paid army, they would centralize their state, avoiding the divergence of boundary regions, and have more loyal and powerful army, and conquer all their neighbors. But they would not do it for one-and-a-half millenium, until Napoleon! =)