"Late bind all the things" is pretty much what Alan Kay's idea of OO was. In particular it means that methods are invoked by name and selected based on message name by the receiving object. Any object can be sent any message; how that message is handled is determined by the object at invocation time. No vtbls or other such mechanisms used by statically typed OO languages are involved.
Kay has spoken positively, for instance, of Erlang, which has nothing like Smalltalk's OO model.
It has, but that can be overcome by thick enough runtime.
My experience is with Common Lisp, which has a quite sophisticated object system (CLOS) with a metaobject protocol. Theoretically, pretty much everything there can be altered on the fly at runtime - classes and methods can be added, modified and deleted, inheritance hierarchy changed, method invocation rules arbitrarily altered, etc. In practice, efficient implementations like SBCL (which tries to eagerly compile everything down to machine code, including at runtime) tend to have a lot of logic for keeping track how how things currently are.
99.9% of the time, the current shape of the object model is fixed, so it's kept optimized in advance. For example, calling (my-method my-obj) can do anything, depending on what my-method, my-obj, (class-of my-obj), etc. are at the moment - however both you and the runtime know that, right now, my-method is only defined on class-foo, which uses standard object model rules, so the runtime ensures the call is just a fixed-address jump. Define my-method for another class, the runtime will make calls to my-method a simple lookup on a tag (or something equivalent). Mess with the method combination order, or class definitions, and the runtime will redo its own book-keeping and keep the calls as efficient as possible. So you still pay for the flexibility - but mostly just-in-time, in the 0.1% of the time you invalidate some optimization, forcing the runtime to re-optimize itself.
I don't have as much experience with Smalltalk, but I hear that the story there is similar - you usually have a fat runtime with gnarly, stateful internals that re-optimizes itself on the fly to keep the flexibility performant. It's a nice benefit of image-based languages, where the compiler is an integral part of the runtime.
I also have concerns about maintaining correctness in this kind of late binding environment; it's useful to be able to statically verify things up front such as through the type system.
Which is why I prefer only being able to opt-in to late-binding where it makes sense: implementations that are late-bound in have to at least satisfy the type checker. Also, depending on environment, some sort of metadata may indicate to future readers/maintainers that late-binding is happening.
Kay has spoken positively, for instance, of Erlang, which has nothing like Smalltalk's OO model.