Yanking a crate better than deleting it
I agree, reusing a crate name is risky.
But here is an idea: when a crate is deleted and after some time (years preferably, not months), someone re-register it, what if existing Cargo.lock would be reported as incompatible? Using a generation counter to prevent the ABA problem.
Like, every time a crate name is reused, it gets an unique name _unique_cratename_N where N is an increasing counter (crate names with this pattern get prevented to be registered). In Cargo.lock, whenever a crate was mentioned was cratename (like all lockfiles today do), it gets interpreted as _unique_cratename_0, which prevents building if the crate were re-registered (since the new crate will be called _unique_cratename_1). But whenever new code depends on cratename, Cargo will generate a Cargo.lock that refers to the right generation counter.
This should probably not be required if the crate being is very new, has no downloads, has no dependencies in crates.io, etc.
There's a problem with this though. This scheme only works with new Cargo - older versions of cargo would be permanently prevented from depending on deleted crates that were later re-registered. (maybe there's a variant of this idea that could accommodate older versions of cargo too)
Discussion in the ATmosphere