Currently Cargo and local Cargo tools can cheaply search crates for all hyphen/underscore variants, because the entire index is kept locally on user's machine. However, this approach doesn't scale well and will fail before crates.io reaches npm's size.
To fix the scalability problem, I've proposed a new registry interface based on static HTTP files that allows downloading only as little of the index as needed. However, that partial access means it's no longer possible to do brute-force search.
So it'd be nice to take this into consideration. For example, the file paths in the index could be changed to always use underscores.