Last week after the most recent Microsoft Updates were applied SharePoint Search stopped working on one of my MOSS Farms. All searches at that the site level would display no results.
Upon checking the SSP I received the following error for each of my SharePoint Content Sources, “Access is denied. Check that the Default Content Access Account has access to this content, or add a crawl rule to this content. (The item was deleted because it was either not found or the crawler was denied access to it.)
After some research I found and followed the registry modifications (Method 1) listed in Microsoft KB 896861 which solved the problem. I believe that Microsoft .NET Framework 3.5 Service Pack 1 was to blame for this but 100% sure of this.