Company Files in Tools are deleted but still showing as duplicate file when try to upload again

I am using Email & Broadcast for individual emails to customers. I have uploaded pdf’s which are proposals and then when it’s been a while, I delete those proposal from within Tools=> Files => Company Files=> Delete. However, if I try to re-upload a formerly deleted company file, I cannot do that and get a message that it’s a duplicate file. But is isn’t showing up in the file toolbox because it was deleted. Please help.