Remote Desktop flaky

I have two computers, alice and bob. Both are running Windows XP SP2 and both are in the same domain. Usually when I reboot bob and then try to log in to it from alice using Remote Desktop, I get "This computer can't connect to the remote computer ". Magically, after I log on locally into bob, remote logon also starts to work. I think the network is not to blame because I can "telnet bob 3389" from alice to bob's terminal server (the command prompt window blanks and there is a blinking cursor in the top left corner). I've searched the web many times already but haven't come across anything like this yet. Although searching for this error message does turn up many relevant pages, I still haven't found a solution. So I'd love to hear if anyone else has had this problem and knows how to fix it.

 

I rebooted bob, tried to connect with it's full domain name and immediately got "This computer can't connect to the remote computer...Remote Desktop cannot find the remote computer ". Telnet gave "Could not open connection to the host, on port 3389: Connect failed ". Using bob's IP address didn't help. Then I logged on locally, didn't help. Then I logged off and now Remote Desktop suddenly works.

I checked the logs but couldn't find any related errors. I wonder why the Terminal Services service does not leave any entries in the log when it starts. It starts because it is obviously running because Remote Desktop works. Terminal Services startup type is set to Automatic, this means that it always starts at boot time, right?

 

I rebooted bob once again. At first with Remote Desktop and full domain name I got an immediate error message "This computer can't connect to the remote computer...Remote Desktop cannot find the remote computer ".

Then I tried telnetting, with success. Command prompt window blanked, blinked the cursor for a while, then after about a minute the text "Telnet" in the title bar of the command prompt window started to flash rapidly and the cmd.exe consumed 100% CPU for a few seconds. After that the telnet apparently quit and I got the prompt back. Then I tried to Remote Desktop to bob with bob's IP address and it worked! It also works if I type just bob into the address field of Remote Desktop Connection. But it still won't work with the full domain name.

I'm starting to think that there is something wrong with the full domain name.

 

Well now Remote Desktop seems to be working all the time no matter how many times I reboot.

I'm suspecting that the previous flakiness might have been caused by the domain name resolving or something. I never entered my password into the "Enter your credentials for ..." credential promting window that appears after you enter the remote computer name. But then I somehow figured that because the plain computer name bob gets me to bob, entering my password could help and it actually did! Now I can connect with bob's full domain name.

Does the domain somehow cache the credentials or what's going on?