Long time ago I wondered about the same. I always thought the Roman army (early imperial, of course) would beat the crap out of any opponent until the end of the middle ages. After learning a lot about history I had to change my opinion completely.
No. 1: The Roman army was entirely professional. From the lowest recruit up to generals in command. Medieval armies were definitely not. That was a professional cadre (nobles, knights and possibly sergeants) leading drafted poorly equipped and poorly trained peasants. And poorly led, certainly in the eyes of Roman professionals.
No. 2: Logistics. That concept went completely down the drain after the fall of Rome in the West. (Do mind that the Byzantine army was a continuation of the Roman army with excellent logistics and survived a millennium). For a professional army you need a lot more than pack a lunch.
It's there that medieval armies fell short. It was something they simply couldn't do, no matter what. You need supplies for the army in the field. Transportation to get it there. Folks back home producing food, arms, uniforms and equipment. I leave out medical services, medieval armies weren't very strong in that department. No medieval state except for Byzantium was capable of doing that.
It took about a year to train a Roman recruit to be a basic legionary. During that year they did nothing else but train. They had to eat now and then, meaning that someone else had to grow the food, harvest it and get it to the legion. Once trained and professional, they had to keep training to remain fighting fit. You can't be a farmer and a professional legionary. It's either - or. Medieval states had no capability for that. Rome and Byzantium did.
Another very important point here: if you hire soldiers full time, until they have to retire due to (relatively) old age at 40-50, you take their best and most profitable years. That means you have to provide them with some sort of pension. That was within medieval society completely impossible.
3- (Very) early medieval armies actually were (very) late Roman armies.
The Roman army varied over time. It adapted itself to the enemies it had to face. From a hoplite army suitable to fight local wars into a more cavalry based relatively mobile army at the end.
During the battle of Chalons against the Huns the Roman army was present but didn't do much. Even Aelius didn't think they were of much use other than be an obstacle. A rather inglorious end for the probably best army ever...