An interesting post. Will have to check out Pandora. As you seem to have a lot of experience: what do you think about the mantra I read here frequently that it's not possible to have good AI with 1UPT?
In Pandora I did not have to deal with the problems of 1UPT.
Pandora has stacks but stacking is discouraged due to AoE-Damage and flanking-boni. So I still had to implemented ways to spread the units out. But it is obviously much easier when they can walk through each other to reach their destination.
I just thought a bit about how I would approach 1UPT.
What has to be done differently is to sort the units for "unoccupied neighbour-tiles" before you go through them.
This way you'd always move the ones with most "Freedom" first, which potentially frees up the others. Once you ran out of units with unoccupied tiles and movement left, you make the ordered list again to consider what has been changed since the other units have moved.
And among those there should be other considerations for move order aswell. Unoccupied-tiles, Movement-Speed, attack-range (but in backwards order: move units with lower attack range first).
Another thing I'd consider is unit-composition. Since you can surround a tile with no more than 6 melee-units, it seems to be rather pointless to have much more than that per target you want to attack at the same time in your army. Maybe some backup to replace losses.
Something along the lines of: If < 6 then 100% melee, for anything over 6 aim for a 1:5 melee:range-ratio.
So overall I'd say:
More algorithmically complex and processing-intense due to several cycles being required required? Definitely.
"Not possible"? definitely not! It's a task that I would consider myself totally capable of being able to do.
There's other games with 1UPT with excellent AI.
For example the Tactics-Game "Battleworld: Kronos" or the Abstract-Strategy-Game "Arimaa" (which has cracy complexity when it comes to unit-interaction).
But I personally did not like 1UPT in Civ 5 from a player-perspective either. It was just annoying when moving larger armies.
I consider Pandora's approach of having stacks but discouraging them with Splash-Damage and encouraging splitting with incentives like flanking to simply be better game design. It does not take away anything about how tactical combats are... I'd even say it adds something!