The observed behaviour is normal because of the late anti-affinity check on the compute node. Because the scheduler only schedules one instance at a time with no knowledge of other instances being scheduled, it cannot take into account anti-affinity rules between two instances in the process of being scheduled. For example, if instance A and B are anti-affined from each other, the scheduler can send them both to compute host X, and only when instance B starts building on X will the late anti-affinity check kick in and send instance B back up to the scheduler.
One thing that we could probably do is not count that kind of reschedule as a failed build. I can bring that upstream, and if it's accepted we could then backport that to 13.
The reason this "worked" in Newton is that back in Newton there was no concept of build failures in Nova.
As a shot-term solution, the BuildFailureWeigher (that controls scheduling of instances to compute nodes with build failures) can be disabled by setting [filter_scheduler]/build_failure_weight_multiplier = 0.
Looks like the discussion is continuing in bz 1701334. I'm going to close this BZ as a duplicate. If this is wrong and there is a bug here that's different from 1701334 to be addressed, by all means please re-open this bz.
*** This bug has been marked as a duplicate of bug 1701334 ***