One of our MOSS 2007 servers has a single Web Application (no extended Web Apps) and is configured to use Basic Authentication. I have confirmed that my dedicated crawl account has sufficient permissions in the Policy for Web Application section of Central Administration > Application management.
I try to start a full crawl of the local SharePoint content but it keeps throwing the following error:
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.)
So I extended the main Web Application and configured it to use Integrated Windows Authentication. I edited the Local SharePoint Content Source and set it to use the URL of the extended Web Application and guess what, it started indexing my content again.
Bottom rule
Always make sure there is a Web Application (extension) configured with Integrated Windows Authentication. You can keep it internal and hidden if you like. Preferably it is the default zone. Public URL's that use a different authentication mechanism should always be configured on an extended Web Application.