I finally got a chance to try and reproduce this on a devstack and can now see what you have reported.

$ git log -1
commit e20e731630c1b337daf4446286bb6c8e761025e3 (HEAD -> master, origin/master, origin/HEAD)
Merge: fc159ac91b 998475f5bd
Author: Zuul <email address hidden>
Date:   Wed Mar 11 19:03:28 2020 +0000

    Merge "nova-net: Remove unused nova-network objects"

I created a server group with anti-affinity policy and booted two servers at the same time in separate terminal windows. (Note that this depends on your timing -- if you are "too slow" you will see one go to ERROR with "No valid host" and the other to ACTIVE because the affinity check at the scheduler will catch it).

$ openstack server group create --policy anti-affinity anti-affinity
$ openstack server group list
+--------------------------------------+---------------+---------------+
| ID                                   | Name          | Policies      |
+--------------------------------------+---------------+---------------+
| 85f266b7-3fe9-492a-b80b-7c74b7ea1a73 | anti-affinity | anti-affinity |
+--------------------------------------+---------------+---------------+
$ openstack server create --image 50668455-013d-4daf-80b3-dc2ae225663f --flavor 42 --hint group=85f266b7-3fe9-492a-b80b-7c74b7ea1a73 --nic net-id=01524af1-e35d-4ed9-a411-1fee224fb07c one
$ openstack server create --image 50668455-013d-4daf-80b3-dc2ae225663f --flavor 42 --hint group=85f266b7-3fe9-492a-b80b-7c74b7ea1a73 --nic net-id=01524af1-e35d-4ed9-a411-1fee224fb07c two
$ openstack server list
+--------------------------------------+------+--------+------------------------+--------------------------+---------+
| ID                                   | Name | Status | Networks               | Image                    | Flavor  |
+--------------------------------------+------+--------+------------------------+--------------------------+---------+
| 8dd746d3-6201-4a3b-a3b1-71c854ff8721 | one  | ACTIVE | shared=192.168.233.168 | cirros-0.4.0-x86_64-disk | m1.nano |
| 6fe23607-0875-498f-b52b-50c910bc1b61 | two  | ACTIVE | shared=192.168.233.240 | cirros-0.4.0-x86_64-disk | m1.nano |
+--------------------------------------+------+--------+------------------------+--------------------------+---------+

BUT then I noticed in the /etc/nova/nova-cpu.conf:

[workarounds]
disable_group_policy_check_upcall = True

This will disable the late affinity check [which preserves affinity policy enforcement in the case of racing parallel requests) in nova-compute.

The default value is False [1] but it is set to True in devstack in the gate [2] because the gate is configured to exercise the multiple cell service topology [3] and run with a "superconductor". With multiple cells with each cell using their own separate message queue, the late affinity check can't work.

But in devstack, there is only a single message queue, so it is possible to use [workarounds]disable_group_policy_check_upcall = False in /etc/nova/nova-cpu.conf. You will want to set this if you want to be able to handle affinity races.

When using [workarounds]disable_group_policy_check_upcall = False with a multi-tier conductor setup, you'll also need to set the [api_database]connection in the cell conductor nova config /etc/nova/nova_cell1.conf (I copied from /etc/nova/nova.conf that n-super-cond is using). 

So trying again, I set [workarounds]disable_group_policy_check_upcall = False in /etc/nova/nova-cpu.conf and restarted devstack@n-cpu and set [api_database]connection = <setting from /etc/nova/nova.conf> in /etc/nova/nova_cell1.conf and restarted devstack@n-cond-cell1:

$ openstack server create --image 50668455-013d-4daf-80b3-dc2ae225663f --flavor 42 --hint group=85f266b7-3fe9-492a-b80b-7c74b7ea1a73 --nic net-id=01524af1-e35d-4ed9-a411-1fee224fb07c one
$ openstack server create --image 50668455-013d-4daf-80b3-dc2ae225663f --flavor 42 --hint group=85f266b7-3fe9-492a-b80b-7c74b7ea1a73 --nic net-id=01524af1-e35d-4ed9-a411-1fee224fb07c two

$ openstack server list
+--------------------------------------+------+--------+------------------------+--------------------------+---------+
| ID                                   | Name | Status | Networks               | Image                    | Flavor  |
+--------------------------------------+------+--------+------------------------+--------------------------+---------+
| eb896048-4c8e-4f2d-a88e-7f7e8fbab489 | one  | ERROR  |                        | cirros-0.4.0-x86_64-disk | m1.nano |
| d9a79bd9-a0dc-42d1-9437-d635bae22a00 | two  | ACTIVE | shared=192.168.233.160 | cirros-0.4.0-x86_64-disk | m1.nano |
+--------------------------------------+------+--------+------------------------+--------------------------+---------+

Looking at the n-cpu log:

Mar 25 20:22:23 ubuntu-bionic nova-compute[4278]: DEBUG nova.compute.manager [None req-1d4c2c9f-a88e-4f4f-bc67-389d6aa5e486 demo demo] [instance: eb896048-4c8e-4f2d-a88e-7f7e8fbab489] Build of instance eb
896048-4c8e-4f2d-a88e-7f7e8fbab489 was re-scheduled: Build of instance eb896048-4c8e-4f2d-a88e-7f7e8fbab489 was re-scheduled: Anti-affinity instance group policy was violated. {{(pid=4278) _do_build_and_r
un_instance /opt/stack/nova/nova/compute/manager.py:2217}}

That ^ is the late affinity check triggering.

$ openstack server show one
...
| fault                       | {'code': 500, 'created': '2020-03-25T20:22:24Z', 'message': 'Exceeded maximum number of retries. Exhausted all hosts available for retrying build failures for instance eb896048-4c8e-4f2d-a88e-7f7e8fbab489.'} |
...

Based on this, there has not been a regression.

Perhaps last time you tried, it was before the devstack config was changed to reflect a multi-cell deployment topology or maybe the timing of the two requests was "slow enough" to fail at the scheduler filter stage.

You can learn more about multi-cell layout and "upcalls" at this doc:

https://docs.openstack.org/nova/latest/user/cellsv2-layout.html#operations-requiring-upcalls

When running with multiple cells, it presently is not possible to enforce affinity policy properly in a race situation. To support this, affinity support needs to be implemented in the placement service.

And I'm going to work on adding an item about this to our troubleshooting doc to help with future questions/bug reports:

https://docs.openstack.org/nova/latest/admin/support-compute.html

[1] https://github.com/openstack/nova/blob/35240b0d8c450c42d6f44be5f1df58d850a020d3/nova/conf/workarounds.py#L135-L136
[2] https://github.com/openstack/devstack/blob/37659927923473c13f4bec88855205d0ee28bcfb/lib/nova#L900
[3] https://docs.openstack.org/nova/latest/user/cellsv2-layout.html#multiple-cells