New Situation
Once I started testing in logging mode the problem had gone away already. There were some hints to HTTPS certificate issues, but nothing really to blame. Neither with nor without logging the problem could be reproduced after two days of questioning me.

The caching works on the base of the requested domain, that is example.org and not openpgpkey.example.org - thus it should not make a difference when you change your setup. There is an initial test for a cached domain status before the resolving process starts. If you want to look yourself: gnupg/dirmngr/server.c:cmd_wkd_get() and domainfo.c.

Reproducibility
The problem cannot be confirmed generic on domain level. I can reproduce the effect with keys shipped from my domain, i.e. email addresses @shimps.de, but the issue vanishes when I try to reproduce it with email addresses @gnupg.org as e.g. Werner's address.

Users landing here looking for help.

This looks like a bug with gnutls which is the only tool that fails :

This ticket is obsolete

Fixed in 2.4.6.

Thank you for the bug report and your patch.

An update FYI

Fixed by changing server as noted above.

Thanks for all the help @gniibe.

It should not be removed as I believe it is required to be compliant:

I'm afraid that your particular configuration would cause the problem of the negotiation.

Note that we now have also an option instead of the workaround from 2015

For various reasons dirmngr requires and implements a full resolver and implements that. This way all DNS queries are passed through Tor. Thus this is a feature and not a bug. The error message could be better but we can only return what SOCKS tells us.

Lot's of things changed in the meantime.

HKP keyservers are anyway out of fashion and thus we won't put anymore effort into his part of the code.

Lot's of changes since 2.4.

See for T6545 for a new request to support IDP.

I have now disabled the rewriting in the 2.4 branch. Those who want to keep the old behaviour may add

I will review the issue. A likely outcome will be to follow your suggestion but to add an option for the old behaviour to avoid further security discussions.