I’m assuming that this is not specific to itertools but is general to other crates as well.
For the searchability part, I think a good search-via-type/function-name mechanism that is cross-crate on docs.rs, similar to what is provided by hayoo and hoogle would be very helpful.
In the far future, RLS could perhaps start searching the ecosystem for a function with the name you are looking for. And rustc could do the same in error-fixing-suggestions if enabled. Tho perhaps this is going too far.
Other than that, a uniform redirection+blessing-approach sounds nice, how about?:
trait Iterator {
...
#![search_advice(does_not_exist, interleave)]
#![search_advice(on_crates_io, interleave)]
#![search_advice(in_crate, itertools::Itertools::interleave,
https://docs.rs/itertools/0.7.4/itertools/trait.Itertools.html#method.interleave)]
#![search_advice(in_crate, itertools::Itertools::interleave,
https://docs.rs/itertools/0.7.4/itertools/trait.Itertools.html#method.interleave,
Some random comment on why this is stable, great and verified)]
}