The way you have described you problems in the past leads me to believe that your base problem is a DNS issue. IIRC you noticed last time that there was a discrepancy between the IP address issued to a machine and it's registration in the DNS system. You noted that fixing the DNS record fixed the issue. That makes me believe that some of your machines are either unable to dynamically update thier own DNS record or that the server isn't accepting dynamic updates to the DNS records. It seems to me that this issue may be related and it's something you need to investigate.
It's not an easy issue to troubleshoot but since it appears to be the root of the problem from where I sit it's definitely an alley I would "wander down"
