For the proof that WS-A joined the domain Please see " System Properties " in the snapshot below
Clearly this scenario would be irrelevant if someone had deleted the computer account from AD.

Ensure that the workstation NIC has the DNS server set as the domain controller IP. The workstation uses DNS to contact the correct domain controller. If the DNS is set to an external server, or a server that does not have the domain controller referenced, then it will never find the DC and it will never be able to enumerate the directory/network. Thus the error message.