It is much, much more plausible than experience with common everyday materials in the macro world would lead you to believe. Experiments have shown that these types of relatively non-specific interactions can and do occur. Proteins can be "sticky". You have to think of them more like "lego" rather than metal, wood or whatever. The molecular evidence overwhemingly supports the idea that the same types of molecular "parts" are found in many different machines. The proteins themselves are essentially combinations of a relatively small set of motifs. Expeiments which address how systems might evolve have been performed in microorganisms. There are several examples of experimental situations where a bacterial population evolves systems (enzymes, regulatory switches etc.) to metabolize foreign substances. I am unsure if anyone has taken these experiments to the point where more complex machines evolve, but it would hardly be surprising.