Vista - Search Displays Deleted File Names (in deleted folder)

Much of the stuff I download from the net goes into one particular folder,
and a search immediately shows it is present.
However, when I remove a file from that folder, the search STILL shows it is
present (its filename, NOT the actual file).
I have tried deleting the entire folder, then reperforming the saved
search...and it does not even acknowledge that the Folder is not there (right
click/refresh does nothing either).
I have tried deleting the search from the saved searches folder AND the
download folder, then reinstating them both...and those blasted filenames
come back (remember these are for files that DO NOT EXIST).
How do I get search to stop messing around (or is this a bug in the system
that only M'soft can fix)?