I was pulling my hair out on this:

A machine came up with IPv6 DNS servers only set in /etc/resolv.conf:

nameserver 2001:4860:4860::8888
nameserver 2001:4860:4860::8844

I tried to import a package signing key via apt-key, which fails by 'Server indicated a failure':

irc ~ apt-key adv -vvv --debug-all --keyserver hkps://hkps.pool.sks-keyservers.net --recv-keys
11E9DE8848F2B65222AA75B8D1820DB22A11534E
Executing: /tmp/apt-key-gpghome.kysTGMG2Wg/gpg.1.sh -vvv --debug-all --keyserver hkps://hkps.pool.sks-keyservers.net --recv-keys
11E9DE8848F2B65222AA75B8D1820DB22A11534E
gpg: using character set 'iso-8859-1'
gpg: enabled debug flags: packet mpi crypto filter iobuf memory cache memstat trust hashing ipc clock lookup extprog
gpg: DBG: [not enabled in the source] start
gpg: no running Dirmngr - starting '/usr/bin/dirmngr'
gpg: waiting for the dirmngr to come up ... (5s)
gpg: DBG: chan_3 <- # Home: /tmp/apt-key-gpghome.kysTGMG2Wg
gpg: DBG: chan_3 <- # Config: [none]
gpg: DBG: chan_3 <- OK Dirmngr 2.1.18 at your service
gpg: connection to the dirmngr established
gpg: DBG: chan_3 -> GETINFO version
gpg: DBG: chan_3 <- D 2.1.18
gpg: DBG: chan_3 <- OK
gpg: DBG: chan_3 -> KEYSERVER --clear hkps://hkps.pool.sks-keyservers.net
gpg: DBG: chan_3 <- OK
gpg: DBG: chan_3 -> KS_GET -- 0x11E9DE8848F2B65222AA75B8D1820DB22A11534E
gpg: DBG: chan_3 <- ERR 219 Server indicated a failure <Unspecified source>
gpg: keyserver receive failed: Server indicated a failure
gpg: DBG: chan_3 -> BYE
gpg: DBG: [not enabled in the source] stop
gpg: random usage: poolsize=600 mixed=0 polls=0/0 added=0/0

outmix=0 getlvl1=0/0 getlvl2=0/0

gpg: secmem usage: 0/65536 bytes in 0 blocks

Turned out, after adding nameserver 8.8.8.8 to /etc/resolv.conf, the key was happily imported, so simply IPv6-only DNS seems
to be broken.