Windows 7, files reappear after deletion

They only appear not to have been deleted, because some other process is still using the file and hasn't finished with it yet.

Take a look at this page at Microsoft's support site:

You cannot delete a file or a folder on an NTFS file system volume

Cause 2: The file is being used

You may not be able to delete a file if the file is being used. To resolve this issue, determine the process that has the open handle, and then close that process.

Depending on how the file is opened (for example, it is open for exclusive access instead of shared access), you may not be able to delete a file that is in use. You can use a variety of tools to help you determine the processes that have open handles to files whenever you want.

[...]

The symptoms of this issue may vary. You may be able to use the Delete command to delete a file, but the file is not actually deleted until the process that has the file open releases the file.

Steam runs continuously in the background, so any files it is using won't be released (and thus properly deleted) until Steam stops running, which is normally only when you log off.

You can use Process Explorer or the handle command (both available from the SysInternals site) to determine which process is still using the file you're trying to delete.

But I don't think it's really a problem - it only looks like a problem. Consider it a display issue.

While researching this problem I found this question first which described my problem in Win7, but did not display a solution (the "bad upgrade" answer was most likely just the disabled service below). Using Process Explorer from the accepted answer pointed me towards "System" (PID 4) keeping the files open, which then lead me to this question:

Why would SYSTEM continue locking executable file handles after the app has exited?

For me the solution was a simple as opening up services.msc and then setting Application Experience to "Automatic".

Disabling indexing could potentially help as well, but that seems like a heavy handed solution and only worth trying if Application Experience is already enabled.