Index: b/g10/getkey.c
===================================================================
--- b/g10/getkey.c
+++ b/g10/getkey.c
@@ -105,6 +105,15 @@
 static user_id_db_t user_id_db;
 static int uid_cache_entries;	/* Number of entries in uid cache. */
 
+
+typedef struct no_uid_list
+{
+  struct no_uid_list *next;
+  u32 keyid[2];
+} *no_uid_list_t;
+static no_uid_list_t no_uid_list_db[32];
+
+
 static void merge_selfsigs (kbnode_t keyblock);
 static int lookup (getkey_ctx_t ctx, kbnode_t *ret_keyblock, int want_secret);
 
@@ -2758,47 +2767,67 @@
 {
   user_id_db_t r;
   keyid_list_t a;
+  no_uid_list_t u;
   int pass = 0;
   char *p;
 
   /* Try it two times; second pass reads from key resources.  */
-  do
+ again:
+  for (r = user_id_db; r; r = r->next)
     {
-      for (r = user_id_db; r; r = r->next)
-	{
-	  for (a = r->keyids; a; a = a->next)
-	    {
-	      if (a->keyid[0] == keyid[0] && a->keyid[1] == keyid[1])
-		{
-                  if (mode == 2)
-                    {
-                      /* An empty string as user id is possible.  Make
-                         sure that the malloc allocates one byte and
-                         does not bail out.  */
-                      p = xmalloc (r->len? r->len : 1);
-                      memcpy (p, r->name, r->len);
-                      if (r_len)
-                        *r_len = r->len;
-                    }
+      for (a = r->keyids; a; a = a->next)
+        {
+          if (a->keyid[0] == keyid[0] && a->keyid[1] == keyid[1])
+            {
+              if (mode == 2)
+                {
+                  /* An empty string as user id is possible.  Make
+                     sure that the malloc allocates one byte and does
+                     not bail out.  */
+                  p = xmalloc (r->len? r->len : 1);
+                  memcpy (p, r->name, r->len);
+                  if (r_len)
+                    *r_len = r->len;
+                }
+              else
+                {
+                  if (mode)
+                    p = xasprintf ("%08lX%08lX %.*s",
+                                   (ulong) keyid[0], (ulong) keyid[1],
+                                   r->len, r->name);
                   else
-                    {
-                      if (mode)
-                        p = xasprintf ("%08lX%08lX %.*s",
-                                       (ulong) keyid[0], (ulong) keyid[1],
-                                       r->len, r->name);
-                      else
-                        p = xasprintf ("%s %.*s", keystr (keyid),
-                                       r->len, r->name);
-                      if (r_len)
-                        *r_len = strlen (p);
-                    }
+                    p = xasprintf ("%s %.*s", keystr (keyid),
+                                   r->len, r->name);
+                  if (r_len)
+                    *r_len = strlen (p);
+                }
 
-                  return p;
-		}
-	    }
-	}
+              return p;
+            }
+        }
     }
-  while (++pass < 2 && !get_pubkey (NULL, keyid));
+
+  if (!pass)
+    {
+      /* Not found but before we look it up we check whether we
+         have the keyid in the no-uid list.  */
+      for (u = no_uid_list_db[keyid[0] % 32]; u; u = u->next)
+        if (u->keyid[0] == keyid[0] && u->keyid[1] == keyid[1])
+          break;
+      if (!u && !get_pubkey (NULL, keyid))
+        {
+          /* The lookup was successful: Get it from the updated cache.  */
+          pass++;
+          goto again;
+        }
+    }
+
+  /* Put it into the no-uid list.  */
+  u = xmalloc (sizeof *u);
+  u->keyid[0] = keyid[0];
+  u->keyid[1] = keyid[1];
+  u->next = no_uid_list_db[keyid[0]%32];
+  no_uid_list_db[keyid[0]%32] = u;
 
   if (mode == 2)
     p = xstrdup (user_id_not_found_utf8 ());