I recently had an issue with a SharePoint Server 2007 farm where the Search service was completely ignoring an entire document library on one of the sites. It was the only issue that we were aware of at the time and it was very odd. We engaged with Microsoft to try to solve the issue. After what seemed like a very long time, we finally solved it.
The answer: Check Response Headers in IIS for your SharePoint Web Applications and ensure that the MicrosoftSharePointTeamServices header is listed with a value that matches your farm’s build number (ie. 18.104.22.16853).
The SharePoint Search service checks Response Headers to identify whether the site is a SharePoint site or not. If this Response Header is not detected, then it will be crawled like a normal site. When a non-SharePoint site is crawled, things like permissions, visibility settings, etc are ignored and some content may not be crawled at all. This was the issue we ran into.
Before adding the Response Header, our CPU was getting maxed out more than normal and crawls were taking a very long time. Now that the Response Headers are in place, the server is much more responsive and crawls take a fraction of the time that they did before! In addition, this issue applies to SharePoint 2007, SharePoint 2010, and SharePoint 2013.