I think I found the source of the issue, it seems that gpg ignores HTTP Redirects:
$ curl --head https://at.or.at/.well-known/openpgpkey/hu/tyyfxn4t6ytctsfpzfogin37su9pzssg HTTP/1.1 200 Connection established HTTP/1.1 301 Moved Permanently Date: Fri, 01 Nov 2019 16:04:32 GMT Server: Apache/2.4.38 X-Content-Type-Options: nosniff X-Frame-Options: sameorigin X-Xss-Protection: 1; mode=block Referrer-Policy: strict-origin Content-Security-Policy: default-src 'self'; script-src 'self'; style-src 'self' 'unsafe-inline'; Location: https://keys.openpgp.org/vks/v1/by-fingerprint/EE6620C7136B0D2C456C0A4DE9E28DEA00AA5556 Content-Type: text/html; charset=iso-8859-1 $ gpg --auto-key-locate clear,wkd,nodefault --locate-key h...@at.or.at gpg: using pgp trust model gpg: error retrieving 'h...@at.or.at' via WKD: No data gpg: error retrieving 'h...@at.or.at' via None: No public key gpg: key "h...@at.or.at" not found: No public key $ curl --head https://at.or.at/.well-known/openpgpkey/hu/tyyfxn4t6ytctsfpzfogin37su9pzssg HTTP/1.1 200 Connection established HTTP/1.1 200 OK Date: Fri, 01 Nov 2019 16:04:26 GMT Server: Apache/2.4.38 X-Content-Type-Options: nosniff X-Frame-Options: sameorigin X-Xss-Protection: 1; mode=block Referrer-Policy: strict-origin Content-Security-Policy: default-src 'self'; script-src 'self'; style-src 'self' 'unsafe-inline'; Last-Modified: Fri, 01 Nov 2019 15:18:42 GMT ETag: "2592-5964a7b2f5880" Accept-Ranges: bytes Content-Length: 9618 Strict-Transport-Security: max-age=157680000 $ gpg --auto-key-locate clear,wkd,nodefault --locate-key h...@at.or.at gpg: using pgp trust model gpg: pub rsa4096/E9E28DEA00AA5556 2015-10-31 Hans-Christoph Steiner <h...@guardianproject.info> gpg: key E9E28DEA00AA5556: "Hans-Christoph Steiner <h...@guardianproject.info>" not changed gpg: Total number processed: 1 gpg: unchanged: 1 gpg: auto-key-locate found fingerprint EE6620C7136B0D2C456C0A4DE9E28DEA00AA5556 gpg: automatically retrieved 'h...@at.or.at' via WKD pub rsa4096 2015-10-31 [C] EE6620C7136B0D2C456C0A4DE9E28DEA00AA5556 uid [ full ] Hans-Christoph Steiner <h...@guardianproject.info> uid [ full ] Hans-Christoph Steiner <h...@at.or.at> uid [ full ] Hans-Christoph Steiner <h...@eds.org> uid [ full ] [jpeg image of size 5375] sub rsa2048 2015-10-31 [E] [expires: 2020-10-29] sub rsa2048 2015-10-31 [S] [expires: 2020-10-29] sub rsa2048 2015-10-31 [A]
