File no longer located in...

I am trying to fix a computer that had a lot of virus or malware on it.
Operating system is Vista
It has 10000 + video files on it in a directory that does not show up
When I search for the files they show up
If I try to delete them I get the message
"File no longer located in C:\Users\A\!. Verify the the item(s) location and try again"
Any help here would be appreciated.