I think the cleanest solution is to never allow the takeover of crates where there still exists a user which has access to the crate. So as long as their github account wasn't deleted, the crate cannot be taken over without action from the user.
If the license allows it or you reimplement the crate from scratch, you can always publish your crate under a new name and users will flock to you if it is an improvement.
What would help is to increase the visibility of maintained, used, compiling crates, by having them appear earlier in the search.
So the number of downloads in the last month and the age of the last update would be additional heuristics added to the "relevance" search.
Additionally, adding some way to display travis badges or the version of rustc used to upload that crate would help users decide between crates. (the latter should have a way to run cargo publish multiple times with the same version and code, but different compilers, so developers can show that their crate runs on older and newer rustc versions, as well as on stable/unstable.