Thanks for reply.

I tried to search the keyserver from comand line. gpg --search <exact mailadress> results in follwing message:

gpg: Kein Schlüsselserver bekannt (Option --keyserver verwenden)
gpg: Suche auf dem Schlüsselserver fehlgeschlagen: Kein Schlüsselserver verfügbar

In Kleopatra settings there is still the IP from my keyserver present (see attached image). The sks webinterface is accessible from my machine and a search for the same term delivers the correct results.

Just registered to report pretty much the same.
I've been using gpg 2 for a long while and it's been doing just fine, up to the point where people started using keys it didn't recognise that require a later version.

I installed gpg4win 3.1.11, and lo and behold, the keys are recognised but now I no longer have key server functionality which makes it very difficult to keep using.

I checked the gnupg installed with gpg4win 3.1.11 and apparently it's gpg (GnuPG) 2.2.19 with libgcrypt 1.8.5 (at least that's what gpg --version tells me)
When trying to use keyservers in any fashion:

gpg: error searching keyserver: Server indicated a failure
gpg: keyserver search failed: Server indicated a failure

My previous installation which wasn't touched still works (using the same gnupg home as the later version since it was an upgrade), which is gpg (GnuPG) 2.0.26 (Gpg4win 2.2.3) with libgcrypt 1.6.2

gpg: searching for "aaron@eff.org" from hkp server keys.gnupg.net
(1) Aaron Jue <aaron@eff.org>

4096 bit RSA key 59AEBAC5, created: 2016-12-09, expires: 2020-12-08

(2) Aaron Mackey <amackey@eff.org>

4096 bit RSA key 33E247D4, created: 2015-09-10, expires: 2019-09-10 (expired)

(3) Aaron Jue <aaron@eff.org>

2048 bit RSA key 7B06DFFA, created: 2014-06-16, expires: 2016-10-24 (revoked) (expired)

(4) Aaron Jue <aaron@eff.org>

2048 bit RSA key 7B06DFFA, created: 2012-10-24, expires: 2016-12-12 (revoked) (expired)

Keys 1-4 of 4 for "aaron@eff.org". Enter number(s), N)ext, or Q)uit > q

I've tried several things. Using command line, using Kleopatra, using enigmail with the new version, all fail to do keyserver things. Pointing enigmail to the older gpg instance makes it work just fine. So there seems to be a bug in gpg4win 3.x and this seemed to be the best matching issue report.

@Moonchild wrote:

using enigmail with the new version

I'm not sure what version of enigmail you're using, but I think more recent versions of enigmail don't rely on GnuPG for anything to do with keyservers -- rather, enigmail uses native thunderbird javascript to interact with the keyservers.

I'm using enigmail 1.9.9 because I'm on a mail client that doesn't use WebExtensions, so it's using gnupg for keyserver stuff. In this case that means I've been able to verify it's a gnupg issue (both Kleopatra and enigmail displaying the same issue as CLI).

I'm honestly surprised this isn't being given any sort of priority.
gnupg for windows is simply broken. Even Kleopatra, its supplied and designated key management application doesn't work re: keyserver communication.

How is someone supposed to do key management without keyserver communications? Manual import and export? Requesting everyone manually send over their public keys?... Manually checking for revocations?...
Please figure out what the problem is and do something about it!

This has not been set high on the priorities, because keyserver access works for most with Gpg4win (and thus GnuPG) on windows. A recent exception has been occurred about a month ago with Let's encrypt expired root certificate. So currently for Gpg4win 3.1.16 you need to update to a newer GnuPG (Version 2.2.32 at time of writing), by installing the simple installer,e.g. https://gnupg.org/ftp/gcrypt/binary/gnupg-w32-2.2.32_20211006.exe

Please report if you still have problems with this combination?

If so, please additionally try the 2.3 simple installer (e.g. available from https://gnupg.org/download/index.html) instead. There have been many improvements to GnuPG (and other Gpg4win parts). The problem maybe gone by now.