On MOSS 2007 SharePoint Farm, with a dedicated index server, after you have installed Windows update, your search crawling is no longer working. Specifically after installing the hot-fix KB 963027.
MS09-014: Cumulative security update for Internet Explorer, has a fix for a vulnerability in NTLM authentication , more details : http://support.microsoft.com/kb/963027
After applying this security update to SharePoint servers, you would observe that if you have any sites which are not using FQDN , it will still be crawled and those sites which has FQDN are not getting crawled and might get following error message:
Access is denied. Check that the Default Content Access Account has access to this content, or add a crawl rule to crawl this content. (The item was deleted because it was either not found or the crawler was denied access to it.)
You will also observe that you are not able to FQDN site from the server, but you are able to browse the site from your client machine.
This can also be caused due to installation of .NET Framework 3.5 SP1
Changes to NTLM authentication for HTTPWebRequest in Version 3.5 SP1 http://msdn.microsoft.com/en-us/library/cc982052.aspx
This KB article explains in details about the issue http://support.microsoft.com/kb/971382
You can also follow the KB article : http://support.microsoft.com/kb/896861