Another proposal: minimalist approach.
A namespaced crate name like naftulikay/rand is only one character different from the current pseudo-namespacing done on crates.io like naftulikay-rand.
So we could have backwards-compatible namespace approach by allowing users to register a prefix like naftulikay-*, so that only owner of the prefix can publish new crates with that prefix.
While this doesn’t address squatting, it does add namespaces in a backwards-compatible way following existing naming conventions. It works with Cargo and the Rust language without any changes, and the implementation only needs relatively small changes to crates.io.