Currently GPG can't look up keys using WKD when the host it's connecting to requires a valid SNI, this means that all WKDs behind things like Cloudflare or similar "shared hosting" are broken.
For example:
gpg2 --auto-key-locate=clear,nodefault,wkd --locate-key taavi@aegrel.ee
The error is also nondescript "General error" which is useless for debugging.
Nope, of course SNI is used. You problem is a different one. For example no root certificate, a server configured to allow only TLS 1.3, or a not supported algorithm. Decent versions of GnuPG print some hints if run with -v. BTW, an easier way to test is to use "gpg --locate-external-key" which basically does the same you did.
If I check for your key I see:
gpg: Note: server uses an invalid certificate gpg: (further info: bad cert for 'openpgpkey.aegrel.ee': Hostname does not match the certificate) gpg: error retrieving 'taavi@aegrel.ee' via WKD: Wrong name
With your version you need to enable a log file in dirmngr.conf; for example
log-file /some/where/dirmngr.log verbose debug ipc,network
Oh, it's using the openpgpkey subdomain because of the CNAME but that's not actually being served by the server.
-v did not seem to change the output of the command, probably have to change the configuration indeed.
Hm, I don't want to remove the CNAME just so that GPG WKD would work, is there a way to fix this? Is there a good reason why after "Advanced"/subdomain lookup it doesn't try "direct"?
If you configure the subdomain in the DNS this will be used. Thus get a cert for it. The old method should not be used and thus if the openpgpkey subdomain exists gpg concludes that the admin is aware of the new scheme.
There's a wildcard CNAME, it's not _really_ configured. It's not a good assumption that a CNAME == configured and it doesn't have a reasonable fallback, IMHO.
From the specs:
Sites which do not use the advanced method but employ wildcard DNS for their sub-domains MUST make sure that the ~openpgpkey~ sub-domain is not subject to the wildcarding. This can be done by inserting an empty TXT RR for this sub-domain.
Which should solve your problem.
Than put something into the TXT - it does not matter and is only used to break the wildcard.
The specs might just want to say that it just expects the wildcard to be broken, not that it expects an empty record.
Limited testing I did right now shows that just adding a TXT worked.