Thank you for your answer ! :)

Yep, I knew about --kill (a bit more violent, but same idea). Unfortunately, most of our users are not so IT friendly; they don't even know what a terminal/shell is. They're just using GPG without knowing it, through their mail client's plugin.
What would be perfect is something I can configure myself in their gpg.conf / dirmngr.conf once to get around the problem "forever".

To get back on the main subject of the ticket ... I don't want to fight on terminology here, but if I ask GPG to retrieve keys from a given server that is reachable and working properly, I expect to have my keys; if I don't, it IS a bug. The fact that the server was unreachable 2 hours ago should be irrelevant here; if it can work right now, it should.

The following post assumes that we want gpg --search to try to search; meaning that we don't want gpg to exit immediately because of the dead marks, without having sent a single network request to anyone.
The post is a bit long; sorry about that.

After a quick look at the code today, here is what happens when searching for a key from servers :

• ...
  • ks_action_search (dirmngr/ks-action.c:142) (here it iterates over the servers given with --keyserver)
    • ks_hkp_search (dirmngr/ks-engine-hkp.c:1396)
      • make_host_part (dirmngr/ks-engine-hkp.c:1002)
        • map_host (dirmngr/ks-engine-hkp.c:453)

in the latest, here is the part that is interesting:

581   if (hi->pool)
582     {
          ...
590
591       /* If the currently selected host is now marked dead, force a
592          re-selection .  */
593       if (force_reselect)
594         hi->poolidx = -1;
595       else if (hi->poolidx >= 0 && hi->poolidx < hosttable_size
596                && hosttable[hi->poolidx] && hosttable[hi->poolidx]->dead)
597         hi->poolidx = -1;
598 
599       /* Select a host if needed.  */
600       if (hi->poolidx == -1)
601         {
602           hi->poolidx = select_random_host (hi);
603           if (hi->poolidx == -1)
604             {
605               log_error ("no alive host found in pool '%s'\n", name);
                  ...
611               return gpg_error (GPG_ERR_NO_KEYSERVER);
612             }
613         }
614 
615       assert (hi->poolidx >= 0 && hi->poolidx < hosttable_size);
616       hi = hosttable[hi->poolidx];
617       assert (hi);
618     }
619   else if (r_httphost && is_ip_address (hi->name))
620     {
        ... (DNS resolution stuff, irrelevant for this subject)
646     }

648   if (hi->dead)
649     {
650       log_error ("host '%s' marked as dead\n", hi->name);
          ...
656       return gpg_error (GPG_ERR_NO_KEYSERVER);
657     }

So basically, for each URI given with --keyserver, ks_action_search calls map_host, which decide what "real host" to use (in case of a pool), and if we should try to query that host (depending on its dead mark). If the host is dead, or if all the hosts of a pool are, map_host returns a GPG_ERR_NO_KEYSERVER that will be propagated back to ks_action_search.
The thing is :

• if we only gave one URI to --keyserver, it will just exit right now (without having actually searched anywhere);
• even if we gave a list of URI, the current implementation of ks_action_search will exit once it got GPG_ERR_NO_KEYSERVER; so if the first server of the list if marked dead, it won't even try the other ones (for details, see the FIXME at ks-action.c:154);

IMHO, the block should be patched as:

@602
          hi->poolidx = select_random_host (hi);
            if (hi->poolidx == -1)
              {
                log_error ("no alive host found in pool '%s'\n", name);
-                   ...
-                return gpg_error (GPG_ERR_NO_KEYSERVER);
+               /* Try our luck with the first host of the pool */
+               hi->poolidx = hi->pool[0];
              }
          }

@648
-    if (hi->dead)
-      {
-        log_error ("host '%s' marked as dead\n", hi->name);
-           ...
-        return gpg_error (GPG_ERR_NO_KEYSERVER);
-      }

The dead mark will still be used to prefer alive hosts to dead ones for pools, but if all the hosts of a pool are dead, or if the "non-pool host" is dead, it will try again to query it, to avoid exiting without doing nothing.