Comment 4 for bug 1690205

They are *all* bootable in UEFI mode. You're running in the case where we started installing fbx64.efi and shimx64.efi to /EFI/BOOT; but both should only be installed in the /EFI/BOOT path when images are built without --removable. You're getting this message because as there is no ubuntu BootEntry when you first start the VM (since you start with an empty firmware when you run things with qemu/OVMF), so fallback is loaded and attempts to generate it -- but we are not yet installing /EFI/ubuntu/boot.csv to give it data to use to generate the new BootEntry.

The real fix for this is to:
a) make sure cloud-image builds pass --removable to grub-install (already being done)
b) SRU grub2/2.02~beta3-4ubuntu3 patches everywhere (bug 1684341)