Attempting to deploy a binary to a location where a different binary is already stored Existing binary

I'm receiving the error below. I see this referred to in other SO posts (here) & I contacted SDL support, but I'm still having trouble fixing the problem. Can someone offer an EASY solution? I think the steps that lead to this are as follows:

1) publish page with link to PDF 1001.
2) Remove PDF 1001 from page & delete it from the CM
3) upload PDF 1002 with same name as 1001.
4) Now if you try & publish you will get the error.

So I need to unpublish PDF 1001 but it has been deleted from the CM. How can I fix this problem? SDL support recommended a fix involving editing the ZIP file generated during the publishing transaction. But I went as far as unpublishing all pages of the publication & verified that they were gone. The error persists...

ERROR: Phase: Deployment Prepare Commit Phase failed, Unable to prepare transaction: tcm:0-11111-66560, Attempting to deploy a binary 1002 to a location where a different binary is already stored Existing binary: 1001:, Attempting to deploy a binary 1002 to a location where a different binary is already stored Existing binary: 1001:, Unable to prepare transaction: tcm:0-13573-66560, Attempting to deploy a binary 1002 to a location where a different binary is already stored Existing binary: 1001:, Attempting to deploy a binary 1002 to a location where a different binary is already stored Existing binary: 1001:

So the file was deleted from CM, but CD still has a reference to it (according to CD it still exists and is still used by something).

You should publish the page after you remove 1001 but before you add 1002. This should remove the reference from the CD database. Then you should be OK to add 1002 and publish the page again.

[EDIT] Sorry, only read now that you say you unpublished everything. Clearly not, as there is still a reference to it... opening a VM, will be back with updates.

[EDIT2] Still don't understand how it remains a conflict if you unpublish, but this is what I observe on my server:

• Add binary to page, publish
  • Reference added to "REFERENCE_ENTRIES" table in CD
• Remove binary from page, publish
  • Reference removed from "REFERENCE_ENTRIES" table, binary deleted
• Unpublish page (after re-adding binary, republishing)
  • Reference removed from "REFERENCE_ENTRIES" table, binary deleted

So, in my case I'm seeing what I would expect. Give it a try publishing the page after you removed the binary, and if possible go check what's in the REFERENCE_ENTRIES table.