NoSuchMethodError and binary compatibility

    Some time ago I received NoSuchMethodError when I was dealing with multiple versions of the same library. I decided to dig into mentioned error's root cause.
Let's assume that we have one version of the class:
v.1.0

public class Compatible {

    public void execute(Object o) {

        System.out.println("Object");

    }
}

and we execute:
v.1.0

public class Main {

    public static void main(String[] args) {
        Compatible c = new Compatible();
        c.execute(new String());
    }

}

The result is obvious. "Object" text is printed to the standard output. Let's rename our method:
v.1.1

public class Compatible {

    public void executeBetter(Object o) {

        System.out.println("Object");

    }
}

and let's try to execute the same binary version of 'Main' method:

Exception in thread "main" java.lang.NoSuchMethodError: compatibility.Compatible
.execute(Ljava/lang/Object;)V
        at compatibility.Main.main(Main.java:7)

So far, so good. Everything is straightforward. The lack of the method or different method name are the most obvious reasons for the mentioned error.
Let's fix it:
v.1.1

public class Main {

    public static void main(String[] args) {
        Compatible c = new Compatible();
        c.executeBetter(new String());
    }

}

Just a simple renaming and everything works as before. But sometimes you can receive such an error even if there is the potentially right method in place.
Let's try with a newer version of 'Compatible'  that is on the horizon:
v.1.2

public class Compatible {


    public void executeBetter(String o) {

        System.out.println("String");

    }
}

This time the method accepts Strings only. However it should work because in 'Main' v.1.1 we call:

        c.executeBetter(new String());

so we use String and we should be safe, right? Unfortunately NOT! 'Main' v.1.1 executed with 'Compatible' v.1.2:

Exception in thread "main" java.lang.NoSuchMethodError: compatibility.Compatible
.execute(Ljava/lang/Object;)V
        at compatibility.Main.main(Main.java:7)

Exactly the same exception as before. The reason for that is:
The method signature that is going to be invoked is determined during compilation time.
We compiled 'Main' v.1.1 with 'Compatible' v.1.1 and then we replaced 'Compatible' v.1.1 with 'Compatible' v.1.2 which is not binary compatible with v.1.1. If we run 'javap -c' against compiled 'Main' v.1.1 we will see the invocation:

      16: invokevirtual #5                  // Method compatibility/Compatible.executeBetter:(Ljava/lang/Object;)V

Let's recompile 'Main' v.1.1 with 'Compatible' v.1.2. Then it works and we have:

      16: invokevirtual #5                  // Method compatibility/Compatible.executeBetter:(Ljava/lang/String;)V

The fact that the method signature which is to be invoked is determined during compilation time has serious implications. It means that even if your code base is the same and you recompile your code with a different version of the library you can end up with totally different byte code.
We observe the situation with different libraries' versions everyday. Let's say we have library A.1.0 which needs library C.1.1 and we also have library B.1.0 which needs library C.1.2. We need to choose either C.1.1 or C.1.2. Maven has built in mechanism for resolving such dependencies but the algorithm is rather simple. We can end up with code that is binary incompatible.
Does our software work by accident?