I have seen this with Roaming proifles and RDP, apparently the file is deleted off the users desktop, but not the copy that is held in their profile. So the next time they login, the copy is returned. (I personally have removed all roaming profiles in favor of just using Folder Re-diretion to get their data backed up. My users do not move from desktop to desktop).
We found the only way to clear this issue was to delete the file from the profile as well as the desktop which required Administrative involvement for every file. Part of the reason we dumped it.