Just ran into the same problem - nothing past 10/4 was showing up, but search results for old files that had been deleted were. The solution for me was that I had started using granular permissions from the top level down about that time and was unaware that by default this trims (hides) everything with non-inherited permissions from the search crawler.
If you go into Site Settings and hit Search Visibility under the Site Administration column you get the options to expose the site back to the crawler. Caveat being that now those items will show up in a search regardless of the user's permission level, although I don't think they can access it from the link.
Otherwise, when I was researching it a few other things came up:
- Restart your server.
- A permissions problem on the spsearch service seemed to be a common solution. This may have also been a problem with me as well, but we had jacked up the Windows SharePoint Services Search's permissions before I found the granular permission thing.
- Someone noted that their content DB had become detached from the spsearch service -- you can see both the account the service is using and the attached content dbs with "stsadm.exe -o spsearch -action list"
To go ahead and reset the search index, run
"stsadm.exe -o spsearch -action fullcrawlstop" and then
"stsadm.exe -o spsearch -action fullcrawlstart"
Good luck.