I 'somehow' managed to continue with the uninstallation of Exchange 2016 CU23...
To be honest: It's not trivial and it's probably not a good idea to fiddle around, especially using ldp.exe, to recover the deleted server object in a production AD. Create a backup beforehand! Always at least double check your changes! I was not careful enough and managed to restore an object to the wrong parent!
There are some descriptions on the internet on how to use ldp.exe to recover deleted objects manually. But you need to go to the tree/Base-DN within ldp.exe:
"CN=Configuration,DC=......"
and descend into:
"CN=Servers,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=domain,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=your,DC=domain,DC=local"
Where you should see the present server objects AND the deleted object that you are looking for!
Double click it and continue:
- Find the "lastKnownParent" in the right part of the ldp.exe window and copy it to a text editor without the trailing semicolon
- Modify the entry almost as most often described...right click and so on...
- Attribute "isDeleted", Value empty, Operation "Delete", Press "Enter" Button
- Recover the original DN from the copied lastKnownParent and the current DN, so it looks like this:
CN=WhateverServernameItShouldHave,CN=Servers,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=domain,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=your,DC=domain,DC=local
- Attribute "distinguishedName", Value should be the recovered original DN, Operation "Modify", Press "Enter" Button
- Check "Synchronous" and "Extended" checkboxes if neccessary and click run
I repeated this procedure on some sub-objects, that I managed to find under "CN=Deleted Objects,CN=Configuration,DC=your,DC=domain,DC=local" by looking for the lastKnownParent property. I've also recovered the objects below "CN=Databases,CN=Exchange Administrative Group (FYDIBOHF23SPDLT),CN=Administrative Groups,CN=domain,CN=Microsoft Exchange,CN=Services,CN=Configuration,DC=your,DC=domain,DC=local", also found in the "Deleted Objects". But I think it may be enough to just recover the server parent object, not really sure about it.
I now ran "Setup.EXE /mode:uninstall /IAcceptExchangeServerLicenseTerms_DiagnosticDataOFF" multiple times and followed up on all other errors that I experienced. They were all about IIS being in a kind of unexpected state (maybe I did something to initially get there?). On the screenshot you can see that the uninstallation continueing after I manually created some missing AppPools (Had to do this repeatedly, cause they will get deleted multiple times when retrying!), the "Exchange Back End" Website and descending applications (hints in the screenshot) without configuring them further...

...yes, it finished ;)

It seems there is nothing else important to do with the server, other than removing it from the exchange organization, removing the object from AD and decommissioning the host itself.
The restored database objects remained. I will figure out, how to get rid of these.