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.