Description of problem:
I deployed the following script and I think that I reproduced the issue:
~~~
#!/bin/bash
if [ $PWD != /home/stack ] ; then echo "USAGE: $0 this script needs to be executed in /home/stack"; exit 1 ; fi

DIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )"
template_base_dir="$DIR"

ntpserver=10.5.26.10  #RH LAB

openstack overcloud deploy --templates \
-e /usr/share/openstack-tripleo-heat-templates/environments/network-isolation.yaml \
-e ${template_base_dir}/network-environment.yaml \
-e ${template_base_dir}/enable-debug.yaml \
--ntp-server $ntpserver \
--neutron-network-type vxlan --neutron-tunnel-types vxlan
~~~

With the following network-environment.yaml
~~~
[stack@undercloud-7 ~]$ tail templates/network-environment.yaml 
  StorageNetworkVlanID: 903
  StorageNetCidr: 172.18.0.0/24
  StorageAllocationPools: [{'start': '172.18.0.10', 'end': '172.18.0.200'}]
  
  DnsServers: ["192.0.2.1"]

  ComputeCount: 1
  ControllerCount: 1
  OvercloudComputeFlavor: compute
  OvercloudControlFlavor: control
~~~

~~~
[stack@undercloud-7 ~]$ templates/deploy.sh 
Deploying templates in the directory /usr/share/openstack-tripleo-heat-templates
~~~

This created a 1+1 overcloud.

* I then scaled down by one node, using this script:
~~~
#!/bin/bash
if [ $PWD != /home/stack ] ; then echo "USAGE: $0 this script needs to be executed in /home/stack"; exit 1 ; fi

if ! [ $# -eq 1 ]; then
  echo "Please provide a uuid for a node that you wish to delete"
  exit 1
fi

uuid=$1

echo "Deleting $uuid"

DIR="$( cd "$( dirname "${BASH_SOURCE[0]}" )" && pwd )"
template_base_dir="$DIR"

openstack overcloud node delete --stack overcloud --templates \
-e /usr/share/openstack-tripleo-heat-templates/environments/network-isolation.yaml \
-e ${template_base_dir}/network-environment.yaml ${uuid}
~~~

And I also reduced the ComputeCount to 0 before running this.
~~~
[stack@undercloud-7 templates]$ grep ComputeCount network-environment.yaml 
  ComputeCount: 0
~~~

~~~
[stack@undercloud-7 ~]$ templates/delete-node.sh
~~~

* I then incremented ComputeCount back to 1 and reran the initial deploy script.
~~~
[stack@undercloud-7 templates]$ grep ComputeCount network-environment.yaml 
  ComputeCount: 1
~~~

~~~
[stack@undercloud-7 ~]$ templates/deploy.sh 
Deploying templates in the directory /usr/share/openstack-tripleo-heat-templates
~~~

This indeed did not add a new compute node. I ran the same scale out a second time, and this did not change anything, neither.

*) I tried to raise ComputeCount to 2 and scaled out once more.
~~~
[stack@undercloud-7 ~]$ grep ComputeCount templates/network-environment.yaml 
  ComputeCount: 2
~~~
Result: no new compute nodes

*) After that, change of `openstack overcloud deploy (...)` to `openstack overcloud deploy (...) --compute-scale 1`, but kept `ComputeCount: 2` 
Result: scale out by 2 nodes

This looks either like a bug / or unsupported configuration. The issue was confirmed in a lab environment and at a customer site.