I've now run into this twice which means I need a way to remember this problem solution.
Windows NTFS has a method for recording Alternative Data Streams with files. When you download files from the Internet IE may add an Alt. data stream that includes the Internet Zone the file was downloaded from. There is a neat PowerShell command for viewing the stream called get-item filename.exe -stream *.
You can use SysInternals stream.exe to view and delete these alternative data streams. I have not found a way to delete streams within PowerShell.
Here is the best article about the topic:
http://blogs.technet.com/b/askcore/archive/2013/03/24/alternate-data-streams-in-ntfs.aspx
Edit:
Found the PowerShell method
get-item <filename> -stream *
remove-item <filename> -stream zone.identifier
