Same problem here on a 2012 MacBook Air 13”. I was running High Sierra, so I backed that up and wiped the drive and fresh installed Catalina (as new as this computer will go). That seemed to do a firmware update during the install, several reboots, etc. But holding D while booting up still sends me to Internet Recovery and then the same error.
I’ve now fresh installed Mountain Lion from Internet Recovery, but the same thing still happens. The nearest Apple Store is a six hour drive to another province, so that’s not an option. Good luck to anyone with this problem.