diff --git a/g10/mainproc.c b/g10/mainproc.c
--- a/g10/mainproc.c
+++ b/g10/mainproc.c
@@ -2134,8 +2134,7 @@
     }
 
   /* If the above methods didn't work, our next try is to locate
-   * the key via its fingerprint from a keyserver.  This requires
-   * that the signers fingerprint is encoded in the signature.  */
+   * the key via its fingerprint or keyid from a keyserver.  */
   if (gpg_err_code (rc) == GPG_ERR_NO_PUBKEY
       && (opt.keyserver_options.options&KEYSERVER_AUTO_KEY_RETRIEVE)
       && keyserver_any_configured (c->ctrl))
@@ -2144,24 +2143,27 @@
       const byte *p;
       size_t n;
 
+      if (DBG_LOOKUP)
+        log_debug ("trying auto-key-retrieve method %s\n", "KS");
+
+      free_public_key (pk);
+      pk = NULL;
+
+      /* Check whether a SHA-1/256 fingerprint is encoded in the v4 or v5
+       * signature.  If not, fall back on the signing keyid.  */
       p = issuer_fpr_raw (sig, &n);
+      glo_ctrl.in_auto_key_retrieve++;
       if (p)
-        {
-          if (DBG_LOOKUP)
-            log_debug ("trying auto-key-retrieve method %s\n", "KS");
-
-          /* v4 or v5 packet with a SHA-1/256 fingerprint.  */
-          free_public_key (pk);
-          pk = NULL;
-          glo_ctrl.in_auto_key_retrieve++;
-          res = keyserver_import_fprint (c->ctrl, p, n, opt.keyserver, 1);
-          glo_ctrl.in_auto_key_retrieve--;
-          if (!res)
-            rc = do_check_sig (c, node, extrahash, extrahashlen,
-                               NULL, &is_expkey, &is_revkey, &pk);
-          else if (DBG_LOOKUP)
-            log_debug ("lookup via %s failed: %s\n", "KS", gpg_strerror (res));
-        }
+        res = keyserver_import_fprint (c->ctrl, p, n, opt.keyserver, 1);
+      else
+        res = keyserver_import_keyid (c->ctrl, sig->keyid, opt.keyserver, 1);
+      glo_ctrl.in_auto_key_retrieve--;
+
+      if (!res)
+        rc = do_check_sig (c, node, extrahash, extrahashlen,
+                           NULL, &is_expkey, &is_revkey, &pk);
+      else if (DBG_LOOKUP)
+        log_debug ("lookup via %s failed: %s\n", "KS", gpg_strerror (res));
     }
 
   if (!rc || gpg_err_code (rc) == GPG_ERR_BAD_SIGNATURE)