"The installed version of the <Module> module is too old to update" makes no sense to site administrators

I encountered exactly this message.

 [error]  The installed version of the /Layout Discovery/ module is too old to update. 
Update to a version prior to 9.0.0 first (missing updates: 
layout_discovery_post_update_recalculate_entity_form_display_dependencies, 
layout_discovery_post_update_recalculate_entity_view_display_dependencies).

It makes no sense a i never had a D8 installed.

Consulted the source. There is a list of performed updates maintained by UpdateRegistry service.
So in my case, This can happen when module install crashes and \Drupal\Core\Update\UpdateRegistry::onConfigSave did not do its job.
According to #3130037-10: system.schema information gets out of sync with module list → module install is not atomic / not in a transaction.

So did that manually and the error is gone:

vendor/bin/drush eval "\Drupal::service('update.post_update_registry')->register
InvokedUpdates(['layout_discovery_post_update_recalculate_entity_form_display_dependencies', 'layout_discovery_post_update_recalculate_entity_view_display_dependencies']);"

FWIW. We ran into this issue with the Module Filter → module upgrading from 4.0.1 to 5.0.0. In that case, the module implements hook_update_last_removed(), after removing some update hooks.

Uninstalling and reinstalling the module appears to fix the issue.