Deploying module removal (files) often results in a configuration that cannot be imported

Modules must be uninstalled with the module code in place to allow various hooks to run (e.g hook_uninstall)

Developers can pick and choose how they go about uninstalling and removing modules. You can simply do it in 2 steps (deploy through the uninstallation, then later composer removal), there is no reason that I can think of where you can't do this.

If you really want to remove it in 1 deployment you can use stub files where you create a stub module directory in your custom modules with nothing but a .info.yml file. This can then be deleted later.

In any case, I don't think this is something that can/should be fixed in core.