We maintain a Windows 2003 Terminal Server for one of our remote offices to connect to to get all their work done. Every morning, when they try to connect, they get an error that the server is unavailable. From our ouwn internal network, we are able to log into that server using RDP just fine. After rebooting the server, the remote office is able to connect once more. It would seem to me (maybe incorrectly though) that given the symptoms the problem isnt with the network (which doesnt change after a reboot) or with all the licenses used up (we are able to log in.) But I have no idea what the problem could be. Any ideas in troubleshooting this will be greatly appreciated.
Additional Information: (5/1/2012)
First, I want to thank everyone who has had suggestions so far. They have been great. So I tested a few things and these were the results: When the connectivity is lost from the outside subnet, I logged into the server locally and attempted to access the subnet. It failed saying "No Network Path Provider was available." Then I did a quick Google search in the browser and after calling up the Google page I was once more able to see the blocked subnet.
We have used the Windows ARP command to check that the MAC addresses of the NIC cards on the server match the ARP cache, and likewise we have checked the Cisco ASA 5500 Router's ARP cache for incorrect entries.