HKPS won't be the reason, we use plain HKP

as of gpg.conf
keyserver hkp://keyserver.int.myCompany.com:11371

BTW. The versions in the previous post should have been 2.0.28 and 2.0.30 vs.
2.1.11, of course.

A collegue of mine now has a similar problem with GnuPG on MacOS during gpg
--refesh-keys from an in-house SKS keyserver (set in gpg.conf)

Happens with GnuPG 2.2.28 and GnuPG 2.2.30. Problem disappeared with GnuPG 2.1.11.
Hence changed category back to gnupg as it's no Windows-only problem anymore.
Still assume that it is somewhat related to larger key rings.

gpg: Total number processed: 392
gpg: unchanged: 392
gpg: keyserver communications error: Not found
gpg: keyserver communications error: Bad public key
gpg: keyserver refresh failed: Bad public key

After some uninstall/install cycles on Win8.1 for several gpg4win versions, I
can tell that only the mentioned gpg4win versions are troublesome as soon as
there's GnuPG 2.0.27+ bundled.

I also tried the plain vanilla gnupg-w32-2.1.11_20160209.exe and everything's
fine, too. As there's no 2.0.x non gpg4win binary on the server, I can't tell if
that's really only a gpg4win whatsoever issue. Pretty strange... For me that's
fine to use, but as most Windows users will stick to gpg4win and the 2.0.x
versions, probably still worth checking.

gpg: Total number processed: 307
gpg: unchanged: 307

C:\Users\mech>gpg --version
gpg (GnuPG) 2.1.11
libgcrypt 1.6.5

Got feedback from users with MacOS GnuPG 2.0.28 and Debian testing GnuPG 2.1.11.
-> not affected despite very similar, if not identical keyring sizes.

So currently only Windows setups having trouble with --refresh-keys.
Will try to get more feedback for Windows with gpg4win.