You have not mentioned whether you have done incremental crawl or Full Crawl.
Incremental crawl will only update the modified files/items in Index- if there are new items added in the source and modified that will be added in the Index. But that would not remove any items that has been removed or deleted from the source.
Full Crawl does crawl entire content source. so here it will remove the items that has been deleted from the content source in addition to the other added or modified and other existing items .
In your case, you will have to analyse the crawl logs carefully. Check what items being deleted from the content source and check the source if that is really exists.
Also check if there was any crawl rules that exists in the search service - this crawl rules sometimes enable you to crawl other items that could not be crawled.
Check the Crawl logs and from there you can get more points to analyse.
Also you need to troubleshoot the crawl using Fiddler , so you will get real time data to analyse and you will get things more clear as and when crawl happens.
Should you need how to use Fiddler for Search crawl troubleshooting,
Every once in a while SharePoint Crawler will behave unexpectedly on web sites that you wish to crawl. You may get error messages that you can understand and help you troubleshoot the problem or you will get just one error that is not helpful at all. Either way, I have found that you can troubleshoot the crawl by using the following technique with Fiddler Web Debugging Proxy (http://www.fiddler2.com). Using Fiddler we are going to configure SharePoint Search to crawl through Fiddler as a Proxy so we can watch the traffic.
Download and install Fiddler on the server running the crawl.
Determine which account is running the crawl. Usually it will be the Default content access account listed in Search Administration:
Armed with the results of the Fiddler trace you can see the conversation that SharePoint is having with the content source that you are troubleshooting. The Fiddler web site has many resources for evaluating the results.
More details mentioned in Matthew's post here : http://www.ableblue.com/blog/archive/2012/01/04/troubleshooting-sharepoint-search-crawl/