Never strange. Always a reason. But, it is frustrating. First, realize that intermittent problems are the hardest to troubleshoot. The fact that it is intermittent makes it nearly impossible to be a firewall issue or a server issue. Good idea to reboot the server, but it should almost never have to be rebooted unless it is mine, then about every other day.
Try these things. And, some of these go against the intermittent issue too, but may as well:
Make sure that remote connections are set up on the computer you are trying to get into. While Remote Desktop is probably checked, you need to make sure you click on Select Remote Users.
Right click My Computer, Properties, Remote.
Local administrators will be selected by default. Domain admins will have access to ALL remote desktops if it is set up to allow remote connections. It's possible that "we" are different people and using different accounts to try to get in. It can get doubly confusing if a user without privileges to get in, never gets in as they should not, and then you are not allowed in for whatever reason and you just think no one can get in. Make sure to add DOMAIN\users, where domain = your domain name.
And, this may sound silly, but don't get Remote Assistance confused with Remote Desktop. I know you wouldn't, but being on the same window can be confusing.
While you hardware firewall needs to be configured to allow access, once it is it doesn't usually change. Windows Firewall is probably configured to do the same, but make sure in Windows Firewall.
On your Remote Desktop Connection go to Advanced and make sure that under Authentication options it says:
Always connect, even if authentication fails. Hopefully, it is NOT as that would be an easy fix.
Under Advanced, Connect from anywhere, Settings, make sure that Automatically detect TS Gateway server settings is selected.
How much memory does the computer you are trying to connect to have? Are there programs running that take up a significant amount of memory? Are you trying to connect while a backup is running? Or an antivirus? RDP connections require that some memory is available to access the desktop.
===================
In order to help troubleshoot these things, it is helpful if you give more information. Start with your network configuration and your IP configs, i.e.
5 XP Pro and 1 Vista Business computers on a server/client network wired. Connected to Internet via a cable modem/Linksys firewall router with a static IP address. Server is a DHCP server for the domain. Use on IP address to access the modem and router. Have hardware firewall, and each client is using Windows Firewall. Server is SBS 2003 Standard Edition R2 if I remember correctly.
HTH.
