[notice] Module {module} has an entry in the system.schema key/value storage, but is not installed

Attempting to update the database, irrespective whether I run update.php or preferred method drush updb the following errors were appearing:

[notice] Module captcha has an entry in the system.schema key/value storage, but is not installed. <a href=":url">More information about this error</a>.
[notice] Module image_captcha has an entry in the system.schema key/value storage, but is not installed. <a href=":url">More information about this error</a>.
[notice] Module recaptcha has an entry in the system.schema key/value storage, but is not installed. <a href=":url">More information about this error</a>.
[notice] Module simple_sitemap has an entry in the system.schema key/value storage, but is not installed. <a href=":url">More information about this error</a>.

So what is happening and importantly how can I correct this error?

What is happening to get ... is not installed error?

At some point a module has been installed and then deleted from the core.extension configuration.  However, the entry in the system schema remains.  Subsequently, it is possible to be left with orphaned entries in the system.schema table.  Sometimes these orphaned entries cause problems with update.php.  Whether causing fatal errors preventing you from being able to run required updates or running updates for the partially uninstalled modules.

How to fix?

Fixing these types of errors, you need to remove the orphaned entries from the system.schema key/value storage system.  Whilst there is no UI for doing this, the best solution is to use drush.  You can write a Drush script to evaluate PHP code that manipulates the system schema table.

Module captcha has a schema in the key_value store, but is not installed.
Module image_captcha has a schema in the key_value store, but is not installed.
Module recaptcha has a schema in the key_value store, but is not installed.
Module simple_sitemap has a schema in the key_value store, but is not installed.

Another type of message you could see is

Module captcha has a schema in the key_value store, but is missing from your site.

The fix here is to run the following command:

drush php-eval "\Drupal::keyValue('system.schema')->delete('{module_name}');"

Obivously you need to replace the {module_name} string.  In the situation like above, this command would be repeated 4 times as follows:

drush php-eval "\Drupal::keyValue('system.schema')->delete('captcha');"
drush php-eval "\Drupal::keyValue('system.schema')->delete('image_captcha');"
drush php-eval "\Drupal::keyValue('system.schema')->delete('recaptcha');"
drush php-eval "\Drupal::keyValue('system.schema')->delete('simple_sitemap');"

Testing time

Check for the error and confirm it has gone.