Forgive me if I misunderstand what you mean by "fail at the type level". If you want the second map.insert(Key::SomeKey); to fail at compile time, this seems like an undecidable problem. Looking at the function signature, there is no indication whether the SomeKey variant already exists in the map:
fn insert(&mut self, key: Key)
The compiler therefore cannot make any guarantees about what the map contains when this method is called. It would be like saying you have let v: Vec<i32> and you want to reduce v.contains(42) to a boolean at compile time for every Vec<i32>.
What have you read so far about the type state pattern? While Rust encourages a type-driven design and has a rich type system, every information is contained in the type itself and there is no meta-state or something similar.
AFAIR this was an idea in the beginning of Rust that was dropped from a language design perspective. It is certain that it is very computationally expensive, even if done well, and generics can (at least partially) emulate it. You could, of course, design your own HashMap that would always give you a new type at insertion that somehow stored the old type (although I wouldn't know how to implement it), but that would be awkward to work with and imo not really worth it.