Why is an explicit dereference required in (*x).into(), but not in x.my_into()?

Interestingly enough, after inspecting the compiler output, it would appear that the Into implementation actually just calls a method of the trait From. What it's looking for is std::collections::From<&Foo> for &str. Therefore, if we implement that trait, the compiler will indeed find our function, and execute it.

Using the following declarations:

#[derive(Clone, Copy, Debug)]
struct Foo();

impl std::convert::From<&Foo> for &str {
    fn from(f: &Foo) -> &'static str {
        "A &str"// This could be replaced with an actual implementation
    }
}

Your code works as you wanted:

let result: &str = (&Foo()).into();// No compiler errors.

The original code you wanted does work, and it isn't actually hard to implement.

Rust performs method lookup exatly as you describe, and it immediately finds a candidate for .into() – the blanket implementation

impl<T, U> Into<U> for T
where
    U: From<T>,
{
    fn into(self) -> U {
        U::from(self)
    }
}

This implementation fulfils all the requirements for candidate methods – it is visible, in scope and defined for type &Foo, since it is defined for any type T. Once the compiler has picked this candidate, it notices that the trait bounds on U are not satisfied, and issues the error you see.

The situation for MyInto is completely different, because you don't provide a blanket implementation based on From. If you do, you will get the same error.

It could be argued that the compiler should skip the blanket implementation if the trait bounds are not satisfied, and move on with the list of candidate types until it finds a better fit. The language specification is actually not completely clear on that point, but from the error we see it is clear what the compiler actually does.