It took me a while to realize that the below error was first related to dirmgr:
$ gpg --search-keys E4053F8D0E7C4B9A0A20AB27DC553250F8FE7407
gpg: error searching keyserver: Server indicated a failure
gpg: keyserver search failed: Server indicated a failure
It took me a bit longer then to realize that the issue was that my router, a R6300v2 replies to SRV queries for _pgpkey-https as a "format error". One can use dirmgr to reproduce the issue:
$ dirmngr
KEYSERVER --resolve
S # hkps://hkps.pool.sks-keyservers.net:443: resolve failed: Server indicated a failure
KS_SEARCH -- E4053F8D0E7C4B9A0A20AB27DC553250F8FE7407
dirmngr[18749.0]: command 'KS_SEARCH' failed: Server indicated a failure <Unspecified source>
ERR 219 Server indicated a failure <Unspecified source>
Using my ISP DNS server (comcat, 75.75.75.75) works, just as using Google DNS (8.8.8.8), however by default these routers are configured by default to tell clients they are the DNS server, and they scrap your request prior to forwarding them to your ISP DNS server.
The Router has the latest firmware: V1.0.4.12_10.0.81 so this likely won't be fixed any time soon...
I've captured through tcpdump what the router replies with, and I'll attach it to the bug report. I've also come up with what I thought would have been a patch to fix the issue, I'll send an RFC to the devel mailing list and refer to this bug report.