As you correctly pointed, one of the reasons for this to fail is a DNS server not updated accordingly. This is surely the most probably reason.
But if I'm not wrong...
The second option you say is also possible. If you're using R77.30 prior JHFA 345 (or an earlier major version), a Security Gateway with IPS enabled and the protection "Non Compliant DNS" set to Prevent may drop the EDNS queries to/from a corporate DNS server. If the protection status is set to Detect or Inactive, then it would not drop it.
Note that, in R77.30, there are two predefined profiles and this protection is set to Prevent by default in the "Recommended Profile".
This does not happen with R80.10 gateways, whatever the status of the "Non Compliant DNS" protection is. So, in case you're using R77.30 and have this protection in Prevent, you should change it to Detect, or to upgrade the Security Gateway. More info about this last option in the sk112578.
So, please check before 1st February if your DNS servers and also your infraestructure is prepared for this change (there is a test option in the link you've sent, 2019 | DNS flag day )