And then check the package ordering ? Look like some random package ordering, or some package not loaded on some machine.
And can you give us your composer version ? I remember that 1.6.x has some bug where they can skip some package “randomly”, if you use the version can you upgrade your composer to have the same version on each machine, and try a fresh install again.
Dominique, thank you very much for your support. I solved the problem with running DistributionUpgrader.phar in the 3rdParty Packages again. There were some composer.json entries left with typo3 ns, which where not rewritten during the first run of the upgrader. Now it works with composer 1.6.x and 1.7 as well.