I thought I've seen this on other releases than Focal, but it turns out that this only affect Focal Pro FIPS images. The latest good (working) image for Pro FIPS Focal has serial 20230613, the first bad (non-working) image has serial 20230614.
The change triggering this bug is https://git.launchpad.net/~cloudware/cloudware/+git/cpc_packaging.extra/commit/?id=a05127df84a038fec657f0302ec0de9636bbf915 .

The debconf entries look good (means empty) before calling "apt-get dist-upgrade --assume-yes --allow-downgrades" which does trigger a shim-signed downgrade. Here's part of the build log with some extra debug messages:


+ echo 'XXXXXXXXXXXXXXXXXX BEFORE XXXXXXXXXXXXXXXXXX'
XXXXXXXXXXXXXXXXXX BEFORE XXXXXXXXXXXXXXXXXX
+ env DEBIAN_FRONTEND=noninteractive chroot /tmp/tmp.ZhjtEWnLTE debconf-show grub-pc
  grub-pc/partition_description:
  grub2/no_efi_extra_removable: false
  grub-pc/mixed_legacy_and_grub2: true
  grub-pc/postrm_purge_boot_grub: false
  grub-pc/timeout: 0
  grub2/unsigned_kernels_title:
  grub-efi/install_devices_disks_changed:
  grub-efi/install_devices_empty: false
  grub2/unsigned_kernels:
  grub-pc/install_devices_failed_upgrade: true
  grub-efi/partition_description:
  grub2/update_nvram: true
  grub-pc/install_devices_disks_changed:
  grub2/linux_cmdline_default: quiet splash
  grub-pc/kopt_extracted: false
  grub-efi/install_devices_failed: false
  grub-pc/chainload_from_menu.lst: true
  grub-pc/hidden_timeout: true
  grub2/kfreebsd_cmdline_default: quiet splash
  grub-pc/disk_description:
  grub-pc/install_devices:
  grub-efi/install_devices:
  grub2/kfreebsd_cmdline:
  grub2/linux_cmdline:
  grub-pc/install_devices_empty: false
  grub-pc/install_devices_failed: false
+ echo 'XXXXXXXXXXXXXXXXXX BEFORE END XXXXXXXXXXXXXXXXXX'
XXXXXXXXXXXXXXXXXX BEFORE END XXXXXXXXXXXXXXXXXX
+ env DEBIAN_FRONTEND=noninteractive chroot /tmp/tmp.ZhjtEWnLTE apt-get dist-upgrade --assume-yes --allow-downgrades
Reading package lists...
Building dependency tree...
Reading state information...
Calculating upgrade...
The following NEW packages will be installed:
  libgcrypt20-hmac libssl1.1-hmac
The following packages will be upgraded:
  libgcrypt20 libssl1.1 openssh-client openssh-server openssh-sftp-server
  openssl
The following packages will be DOWNGRADED:
  shim-signed
6 upgraded, 2 newly installed, 1 downgraded, 0 to remove and 0 not upgraded.
Need to get 3945 kB of archives.
After this operation, 631 kB disk space will be freed.
[snipped]
Setting up shim-signed (1.40.7+15.4-0ubuntu9) ...
Trying to migrate /boot/efi into esp config
Installing grub to /var/lib/grub/esp.
Installing for x86_64-efi platform.
Installation finished. No error reported.
Installing grub to /var/lib/grub/esp.
Installing for x86_64-efi platform.
Installation finished. No error reported.
[snipped]
+ echo 'XXXXXXXXXXXXXXXXXX AFTER XXXXXXXXXXXXXXXXXX'
XXXXXXXXXXXXXXXXXX AFTER XXXXXXXXXXXXXXXXXX
+ env DEBIAN_FRONTEND=noninteractive chroot /tmp/tmp.ZhjtEWnLTE debconf-show grub-pc
  grub-pc/kopt_extracted: false
  grub-pc/install_devices_failed: false
  grub2/linux_cmdline:
  grub-pc/chainload_from_menu.lst: true
  grub-pc/install_devices_disks_changed:
  grub-pc/hidden_timeout: true
  grub2/kfreebsd_cmdline_default: quiet splash
  grub2/kfreebsd_cmdline:
* grub-efi/install_devices: /dev/disk/by-id/dm-name-loop3p15, /dev/disk/by-id/dm-name-loop3p15
  grub-efi/partition_description:
  grub2/unsigned_kernels_title:
  grub-pc/install_devices_empty: false
  grub-pc/disk_description:
  grub2/no_efi_extra_removable: false
  grub-efi/install_devices_disks_changed: /dev/disk/by-id/dm-name-loop3p15, /dev/disk/by-id/dm-name-loop3p15
  grub-pc/postrm_purge_boot_grub: false
  grub-pc/install_devices:
  grub-pc/install_devices_failed_upgrade: true
  grub-efi/install_devices_failed: false
  grub-efi/install_devices_empty: false
  grub2/unsigned_kernels:
  grub2/update_nvram: true
  grub2/linux_cmdline_default: quiet splash
  grub-pc/mixed_legacy_and_grub2: true
  grub-pc/partition_description:
  grub-pc/timeout: 0
+ echo 'XXXXXXXXXXXXXXXXXX AFTER END XXXXXXXXXXXXXXXXXX'
XXXXXXXXXXXXXXXXXX AFTER END XXXXXXXXXXXXXXXXXX


So shim-signed will be downgraded and that triggers the postinst script which runs  /usr/lib/grub/grub-multi-install if /boot/grub/${grubarch}/core.efi exists (see https://git.launchpad.net/ubuntu/+source/shim-signed/tree/debian/shim-signed.postinst?h=applied/ubuntu/focal-updates#n164 )

Given that this file (core.img) does exist when running shim-signed postinst, this triggers the code path for "Trying to migrate /boot/efi into esp config" which does set the debconf grub-efi/install_devices entries. See https://git.launchpad.net/ubuntu/+source/grub2/tree/debian/grub-multi-install?h=applied/ubuntu/focal-updates#n262 .

A possible fix would be, to move /boot/grub/${grubarch}/core.efi away before shim-signed will be downgraded and move it back after the downgrade. but that feels like a hack.
Any better ideas?