The cause of the problem may be lack of available RAM, such as if you're running multiple programs.
In this case, Windows Explorer will not refresh automatically, thus making it appear the file hasn't been deleted.
Pressing F5 (refresh) should work, if not, restart your computer.
Source:
SOLVED - Could not find this item when deleting files - Windows 7