“A Windows workstation was reinstalled. The original domain machine trust account was deleted and added immediately. The workstation will not join the domain if I use the same machine name. Attempts to add the machine fail with a message that the machine already exists on the network I know it does not. Why is this failing?”

The original name is still in the NetBIOS name cache and must expire after machine account deletion before adding that same name as a domain member again. The best advice is to delete the old account and then add the machine with a new name. Alternately, the name cache can be flushed and reloaded with current data using the nbtstat command on the Windows client:

C:\>  nbtstat -R