Любопытно, что проблема решена сама собой, когда я открыл диспетчер загрузки UEFI (F2 во время загрузки) и сбросил заводские настройки по умолчанию.
Предполагаю, что в какой-то момент я включил «Быстрая загрузка» или некоторые такая функция отключила поиск «незарегистрированных» загрузочных разделов UEFI. Запуск grub-update (который вызывает efibootmgr) по существу регистрирует GRUB с менеджером загрузки UEFI, поэтому ему не нужно его искать, но поскольку эта команда еще не запущена на клонированных машинах, efibootmgr и поэтому установка GRUB не будет в списке диспетчера загрузки.