fossil paravians like _Archaeopteryx_ and _Microraptor_ (which retained a medially-directed hallux)
Oh no. They retain a _cranially_ directed hallux. A medially directed one is found in *Confuciusornis* (and for instance the kiwis).
Somebody should have a look at *Changchengornis* and the scansoriopterygids. The latter have a pretty long and fully descended hallux...