Drupal\Component\Plugin\Exception\PluginNotFoundException The "<some_xntt_type>" entity type does not exist.

Problem/Motivation

When developing the External Entities module, I came several times accross this type of issue:
Drupal\Component\Plugin\Exception\PluginNotFoundException The "<em>some_xntt_type</em>" entity type does not exist.
Usually, it happened after running an update and clearing the cache and is related to an external entity type I removed a while ago. For some reasons, there are still traces of that type at some places in Drupal "cache" which is not cleared and Drupal is looking for that type when re-populating new cache. But that type does not exist anymore which leads to a site crash.

Steps to reproduce

It's hard to reproduce since I did not identify yet when it happens.

Proposed resolution

For people coming across this issue, there are several ways to solve it. You could restore a backup before the problem appears, create a temporary external entity with the same machine name, clear the cache and remove that temporary entity. You could also use the External Entity Manager feature "Integrity" check (admin/structure/external-entity-types/integrity) which solves that issue which is related to entity fields in fact.
Otherwise, you could use the following code in a Drupal shell (drush):

$cf = \Drupal::service('config.factory');
$names = $cf->listAll('core.entity_view_display.');
$lost = [];
foreach ($names as $name) {
  if (preg_match('/^core\.entity_view_display\.(\w+)/', $name, $match)) {
    try {
      \Drupal::service('entity_type.manager')->getDefinition($match[1]);
    } catch (\Drupal\Component\Plugin\Exception\PluginNotFoundException $e) {
      // Entity does not exist.
      echo "LOST: " . $match[1] . "\n";
      $lost[$match[1]][] = $name;
    }
  }
}
foreach ($lost as $lost_entity => $lost_confs) {
  foreach ($lost_confs as $lost_conf) {
    $conf = $cf->getEditable($lost_conf);
    $conf->delete();
  }
}

$cs = \Drupal::service('config.storage');
$a = $cs->listAll();
foreach ($a as $conf_name) {
  $conf = $cf->getEditable($conf_name);
  foreach (array_keys($lost) as $lost_type) {
    if ($lost_type == $conf->get('targetEntityType')) {
      $conf->delete();
    }
  }
}
$groups = ['entity.definitions.installed', 'entity.definitions.bundle_field_map'];
foreach ($groups as $group) {
  $key_list = \Drupal::service('keyvalue')->get($group);
  $key_values = $key_list->getAll();
  foreach ($key_values as $key => $value) {
    foreach (array_keys($lost) as $lost_type) {
      if (0 === strpos($key, $lost_type)) {
        $key_list->delete($key);
      }
    }
  }
}

Sometimes, it is not enough and you'll have to investigate a database dump and see where traces of the remove external entity type are still (often in the cachetags, config or key_values tables).
I think it is related to dependencies that are or were not properly set when the external entity type was created. I think the problem is gone with newer versions of external entities but if you update an old site or if I'm wrong and it is still there, you may come across this issue and may have solve the problem so I post this issue for that case. Please, don't hesitate to report here if you met this issue, if it was on an external entity type created and removed on a recent version of external entities and what you did to solve the issue. Thanks.