I had problem detecting clients if they were already on the server before and I removed them on the server and wanted to add them again. They were stuck in Client discovery hints.
Played with it for some time, happened both on physical machines and when I tested on VMs.
In the end it was my expectation that they get recognized instantly like the initial case.
If I let them sit both on the network and came hour later they were added without any need to manually add them, again both in the real world and in VMs testing.
Probably not OPs case since reinstall of server and client happened, but maybe someone who will google this stuff later on like I did.