New config introduced by an update hooks breaks deployment

Problem/Motivation

By following the recommended order of deployments steps :tm: and having this update hook, what you get on a downstream project is this. Where is the issue? AFAIK the update hook cannot check if the config already exists, because it does not. It creates a config with a different UUID which leads to this error when drush cim runs.

[2021-08-26T09:07:45.904Z] + ./vendor/bin/drush -y config:import
[2021-08-26T09:07:48.545Z] +------------+------------------------------+-----------+
[2021-08-26T09:07:48.545Z] | Collection | Config                       | Operation |
[2021-08-26T09:07:48.545Z] +------------+------------------------------+-----------+
[2021-08-26T09:07:48.545Z] |            | admin_toolbar_tools.settings | Create    |
[2021-08-26T09:07:48.545Z] +------------+------------------------------+-----------+
[2021-08-26T09:07:48.545Z] 
[2021-08-26T09:07:48.545Z]  // Import the listed configuration changes?: yes.
[2021-08-26T09:07:48.545Z]
[2021-08-26T09:07:49.456Z]  [notice] Synchronized configuration: create admin_toolbar_tools.settings.
[2021-08-26T09:07:50.799Z]  [notice] Finalizing configuration synchronization.
[2021-08-26T09:07:50.799Z]  [error]  Drupal\Core\Config\ConfigException: Errors occurred during import in Drush\Drupal\Commands\config\ConfigImportCommands->doImport() (line 247 of /mnt/enc-data/www/internal.bnp.devportal.io/vendor/drush/drush/src/Drupal/Commands/config/ConfigImportCommands.php).
[2021-08-26T09:07:50.799Z]
[2021-08-26T09:07:50.799Z] In ConfigImportCommands.php line 261:
[2021-08-26T09:07:50.799Z]               
[2021-08-26T09:07:50.799Z]   The import failed due to the following reasons:
[2021-08-26T09:07:50.799Z]   Deleted and replaced configuration "admin_toolbar_tools.settings" 

Fun fact, you can find similar comments, even videos related to the same error but with config entities, but checking if config synching is running won't solve this problem:

https://www.youtube.com/watch?v=qV2Z0_opyHs
+ see related issues.

Steps to reproduce

Proposed resolution

Remaining tasks

User interface changes

API changes

Data model changes

Release notes snippet