Fichiers supprimés apparaissant en recherche

Bonjour, voilà mon problème (même s'il n'est pas bien grave^^). Je suis sous wndows vista, et certains fichiers que j'ai supprimés (de la corbeiller également) apparaissent lorsque je fais une recherche. Lorsque je clique dessus pour les supprimer, 2 solutions :
- soit ils disent que l'emplacement a été supprimé, me demande si je veux le recréer. Je fais ok, et alors je peux supprimer ensuite.
- soit ils me disent que l'élément est introuvable et je ne peux supprimer. Cependant il reste quand même dans la recherche...
Est-ce normal ? Que faire ?

(merci de détailler vos réponses, je n'y connais pas grand chose en informatique)