Same issue happening with iOS 16.3.1. What I did? I have an iPhone 11 and 2 MacBooks -> Converted the iPhone 11 into supervised device with Apple Configurator -> Still allowUnpairedExternalBootToRecovery is Disabled -> Took another Mac(2nd Mac) with which the device was not connected previously -> Connected the iPhone to 2nd Mac. -> Tried to enter iPhone into recovery mode -> Mac prompted to trust the device. Granted Trust and I was able to restore the device. Please note that I didn't trust these Mac from the iPhone. It was only trusted from Mac side and still I was able to recover the iPhone