(I'm answering this thread because it's one of the first results in Google and doesn't have an answer)
The basics, for SP newbies:
- If you have issues with your search results in the results page, then always start by checking if you have the same issues in the search box just above the list (in the "all items" view, preferably). If that searchbox doesn't give you the expected results, then you have an actual issue.
- Go check the crawling logs in the Central Admin, if you can.
Once it's been proven that some items have the "This item was deleted because its parent was deleted" error, then some people have suggested the following causes :
- the list has the "can't get crawled" setting on.
- The crawler account (the one used by the crawling service) has issues connecting to that list. It could be network issues for example, because that list has a URL that gets blocked by some internal firewall of your company. For that, use Fiddler to investigate (google it, someone has explained the method to troubleshoot sharepoint's crawling network issues quite thoroughly).
- The list has specific permissions. It gets crawled but then the crawler deletes it and all its items recursively because it decides that the permissions are not right.
- The list is somehow broken (sharePoint black magic as we all know it). If you can't reset the index, or if the issue keeps reappearing, then try to delete and recreate the list.
- The list contains some faulty data that does not confuse SharePoint displays/views, but does confuse the crawler. For example, check your list columns thoroughly, and try to detect oddities regarding managed metadata columns and whatnot. Check both column settings and actual data in the list.
When you troubleshoot, check out the crawling logs to find out if the entire list causes crawling errors or only some items in it.
I know it's not an accurate answer but that's all I've managed to gather here and there.