On a system where I have been successfully mixing stable & backports I hit the same dependency problem. So I think this is a recent change. I tried to dig a bit further to see if I could flush out the cause.
TL;DR libegl1-glvnd-nvidia, which I previously installed from backports, is only in stable and not (any longer) in stretch-backports. Does this imply the dependencies of the backported nvidia-egl-icd need to be tweaked (drop libegl1-glvnd-nvidia)? Gory details: # apt -t stretch-backports install nvidia-egl-icd Reading package lists... Done Building dependency tree Reading state information... Done Some packages could not be installed. This may mean that you have requested an impossible situation or if you are using the unstable distribution that some required packages have not yet been created or been moved out of Incoming. The following information may help to resolve the situation: The following packages have unmet dependencies: nvidia-egl-icd : Depends: libegl1 (>= 0.2.999) but it is not going to be installed or libegl1-glvnd-nvidia but it is not going to be installed E: Unable to correct problems, you have held broken packages. # apt-cache show nvidia-egl-icd | grep Depend | sed -e 's/, /\n/g' Depends: nvidia-egl-common libegl1 (>= 0.2.999) | libegl1-glvnd-nvidia libegl-nvidia0 (= 390.77-1~bpo9+1) Depends: nvidia-egl-common libegl1xxx (>= 0.2.999) | libegl1-glvnd-nvidia libegl-nvidia0 (= 390.48-2~bpo9+3) Depends: nvidia-egl-common libegl1 (>= 0.2.999) | libegl1-glvnd-nvidia libegl-nvidia0 (= 384.130-1) # dpkg -l libegl1 libegl-nvidia0 Desired=Unknown/Install/Remove/Purge/Hold | Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend |/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad) ||/ Name Version Architecture Description +++-======================-================-================-================================================= ii libegl-nvidia0:amd64 390.48-2~bpo9+3 amd64 NVIDIA binary EGL library un libegl1 <none> <none> (no description available) # dpkg -l libegl1xxx libegl1-glvnd-nvidia Desired=Unknown/Install/Remove/Purge/Hold | Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend |/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad) ||/ Name Version Architecture Description +++-======================-================-================-================================================= ii libegl1-glvnd-nvidia:a 390.48-2~bpo9+3 amd64 Vendor neutral GL dispatch library -- libEGL un libegl1xxx <none> <none> (no description available) So as a starting point I have libegl1-glvnd-nvidia installed, instead of libegl1xxx or libegl1 (neither of which were ever installed). It seems that for some reason apt now wants libegl1 in preference to libegl1-glvnd-nvidia, despite the latter being the latest version. The preferences scoring comes out like this: # apt-cache policy libegl1 libegl1: Installed: (none) Candidate: 1.0.0+git20180308-2~bpo9+1 Version table: 1.0.0+git20180308-2~bpo9+1 200 200 http://debian-archive.atnf.csiro.au:9999/debian stretch-backports/main amd64 Packages # apt-cache policy libegl1-glvnd-nvidia libegl1-glvnd-nvidia: Installed: 390.48-2~bpo9+3 Candidate: 390.48-2~bpo9+3 Version table: *** 390.48-2~bpo9+3 100 100 /var/lib/dpkg/status 384.130-1 990 990 http://debian-archive.atnf.csiro.au:9999/debian stretch/non-free amd64 Packages So it looks like libegl1-glvnd-nvidia has been removed from the backports suite? I checked what explicitly installing all the packages that can be upgraded would do, which may be of interest. # apt --simulate -t stretch-backports install `cat upgradable` Reading package lists... Done Building dependency tree Reading state information... Done The following additional packages will be installed: glx-alternative-mesa glx-alternative-nvidia glx-diversions libdrm-amdgpu1 libdrm-common libdrm-intel1 libdrm-nouveau2 libdrm-radeon1 libdrm2 libegl1 libegl1-mesa libgl1 libgl1-mesa-dri libgl1-mesa-glx libglapi-mesa libgles2 libgles2-mesa libglvnd0 libglx-mesa0 libglx0 libllvm6.0 libwayland-egl1 libwayland-egl1-mesa update-glx Recommended packages: libcuda1-i386 nvidia-settings nvidia-driver-libs-i386 libopengl0 | libopengl0-glvnd-nvidia libgles-nvidia2 nvidia-egl-wayland-icd nvidia-vulkan-icd The following packages will be REMOVED: libegl1-glvnd-nvidia libgl1-glvnd-nvidia-glx libglvnd0-nvidia libglx0-glvnd-nvidia The following NEW packages will be installed: libdrm-amdgpu1 libdrm-common libdrm-intel1 libdrm-nouveau2 libdrm-radeon1 libegl1 libgl1 libgl1-mesa-dri libgles2 libglvnd0 libglx-mesa0 libglx0 libllvm6.0 libwayland-egl1 The following packages will be upgraded: glx-alternative-mesa glx-alternative-nvidia glx-diversions libcuda1 libdrm2 libegl-nvidia0 libegl1-mesa libgl1-mesa-glx libgl1-nvidia-glvnd-glx libglapi-mesa libgles2-mesa libglx-nvidia0 libnvidia-cfg1 libnvidia-eglcore libnvidia-fatbinaryloader libnvidia-glcore libnvidia-ml1 libnvidia-ptxjitcompiler1 libwayland-egl1-mesa nvidia-alternative nvidia-driver nvidia-driver-bin nvidia-driver-libs nvidia-egl-icd nvidia-kernel-dkms nvidia-kernel-support nvidia-smi nvidia-vdpau-driver update-glx xserver-xorg-video-nvidia 30 upgraded, 14 newly installed, 4 to remove and 72 not upgraded. ... Vince