When I read this post, I zeroed in on:   So, “I need to be sure that when I get rid of an object of this class, the cleanup happens immediately.”   And my strong recommendation is:   “find a way not to have to care about that.”

Reading further, I see that the core problem is that, to this application, “keys” are actually not “temporally unique” at all.   As the OP says, “the same key may come back fairly soon.”   The application obviously has no control over this:   the key, in other words, whatever it may be, is originating from the business.

When something like this happens ... and it does happen a lot in the real world ... I normally solve the problem by treating these “external” keys as surrogate keys.   I do not use them to “uniquely” identify the records that the application must store, knowing that (for my technical purposes) they might not be unique.   Instead, I generate truly-unique, internal-only keys for the records that I need to store, and I map the business-provided keys to them.

Very importantly:   it may well be that there is not a “one-to-one relationship” between the business-provided keys and my internal, known to be really-unique, mappings.   (Should be ... “always” swear-to god-and hope-to die should be ... but there ain’t.)   And so, ever so much more importantly, in spite of this “inconvenient truth,” my application nevertheless did not fall-down and burn in some kind of “I never thought this could happen to me” heap.   The business might have screwed-up, but I’m still standin’.   “Priceless.”

Business-provided identifiers do all sorts of weird things in real life, because human beings are responsible for every bit of it.   Well, humans can deal with that sort of thing; computers can’t.   So, you have to find a way that the computer can, because in any argument between the computer and a human, the computer is the one that has to budge.

Even when designing the internal storage architecture, I try to avoid having many references-to the same “storage object.”   Instead, I assign each object a (application-generated, not disclosed to anyone) random truly-unique key, and refer to it elsewhere using that key.   Yes, that involves an additional hash-lookup.

If the business’s way of handling “an identifier” is posing problems to your application ... don’t try to fancy-pants program around it:   instead, map what you are given to something else (which you give to no one) which does meet the computer’s requirements.   Whatever you do, stay on your feet.