Verwenden Sie den Befehl gpg-connect-agent --dirmngr 'keyserver --hosttable' /bye, um den aktuellen Pool der verwendeten Keyserver zu überprüfen. Sie werden vermutlich feststellen, dass Sie den Schlüsselserver, den Sie erreichen möchten, nicht wirklich per Ping erreichen können.
Die wahrscheinlichste Ursache sind Netzwerkkonfigurationsprobleme. GnuPG könnte beispielsweise denken, dass Sie eine (teilweise konfigurierte) IPv6-Verbindung haben, die tatsächlich unterbrochen ist und dies bevorzugt.
Ändern Sie dann Ihren Keyserver in einen, zu dem Sie eine Verbindung herstellen können.