Are they .doc files? Those are temporary files created by Word. The solution is, of course, to close Word. If some are still leftover after closing Word, you should at least be able to delete them once that they're no longer in use.
There are other programs that use tildes to indicate temporary files, but it's not altogether that common. If the files are temporary files for another program, and you find that you can't delete them even after you close the program, you might have a better chance doing it if you restart your computer and then delete them before starting up the program.
That's interesting to hear. I have no trouble renaming/deleting leftover ~$.doc files on my machine, even if I log in to a non-administrative account.
It sounds to me like the reason they can't be found is probably related to whatever specific turn of events caused them being left behind in the first place. I still don't have a solution, but here's some more questions to help narrow it down.
Are the files in a networked (shared) folder?
Are there any ~$.doc files that you can rename? (check both old and recent ones, and those in other folders as well)
Does the File not found error also happen if you open a ~$.doc file in Notepad?
What about if you copy one of the files and paste it elsewhere? Does it let you paste, and if so, can you modify the new file?