it seems logical (to me) though to assume that any reg entries (or equivalent) that pointed to a non-existent file would have no effect
-Target
You are right but it also seems logical that the file must be hiding some where for it to be rewritten, the cache seems a logical place but if you have cleaned the cache and searched the computers it much be
1, Some where else.
2, Renamed.
Have you removed it from the server where you where distributing it, if uses have installed it from the server then it will not be on their computers and it will reinstall from the server.
Often when I download something I will rename to give it a more meaning full name to me, if this has been done the name you give it would not turn up in a search, The uses may not think about telling you they have renamed it.
Try deleting the files again remove the computer from the network (by unplugging the cable) and restarting the computer then check it the file has returned, if it has it is on the local computer if not then it is on the network. (You can do this if you do not have domain logins and everything is local)
If you have domain logins you may have to create a local login and make sure it is happening with the local login before doing the above. (copy everything from C:\Documents and Settings\%username% to the local user name and and test first you may (or may not) need to change the network settings and password for the new local user name).
This may work and it may not I am not to sure but if it does you will know if the file is local or not.
Edit: PS clean the cache after removing the computer from the network and before restarting.