Useful commands:
virsh net-list
virsh net-info default
virsh net-dhcp-leases default
virsh list
virsh domifaddr <domain>
virsh net-dumpxml default
virsh dumpxml <domain>
Why? What the flip? The MAC addresses are different! Logging into each box and requesting a new lease only worked temporarily. Something was wrong...
And for the solution see: https://superuser.com/questions/1338510/wrong-ip-address-from-dhcp-client-on-ubuntu-18-04
The lease is given per Client-ID (not per MAC), and Client-ID is derived from /etc/machine-id, and that file is the same on all VMs!
Just tweak /etc/machine-id and reboot. Hey presto, new IPs!
Many thanks to stefanha at irc://irc.oftc.net/#virt