WDS stopped working – no servers under Windows Deployment Services 2008 R2

I have three Windows 2008 R2 servers with MDT and WDS installed.
It was reported multicasting stopped working on all of them.
I made sure the multicast option was selected in the deployment shares' properties, but when I went to Windows Deployment Services in server manager, there were no servers showing there. When I tried to add local computer I got the "A directory service error has occurred" error.

The WDS service was running, though, and I was able to restart it, but it didn't help. I rebooted the server, then uninstalled WDS, rebooted again and reinstalled it, rebooted once more. WDS appeared again, but there was still no server under the servers node and I still couldn't add any getting the same error. Also, after reinstalling WDS, the WDS service won't start at all now.

I tried running the below commands, but they failed throwing the "directory service error", I just because there was no server added:

wdsutil /uninitialize-server
wdsutil /initialize-server /reminst:[PATH_TO_REMOTEINSTALL_DIRECTORY]

I enabled tracing and when trying to start the WDS service I get a bunch of errors in WDSServer.log, but I believe they might be irrelevant, and all boil down to no server showing under the "Servers" node.
I found a similar thread here https://social.technet.microsoft.com/Forums/windows/en-US/265b4b53-63ac-491f-817c-6030daa39b81/cant-start-quotwindows-deployment-servicesquot-service?forum=itprovistadeployment, but the suggested solutions don't work for me, as explained above.

It puzzles me that all three servers lost the WDS functionality, can it be something related to AD? I made sure domain, DNS servers etc. are pingable and the computer accounts have necessary privileges set in AD.

I searched the internet high and low, but couldn't find any information on exactly such an issue, so any help will be greatly appreciated.