Under ambient conditions, almost all metals are coated by an oxide. These coatings, the result of a chemical reaction, are not passive. Many of them bind, activate and modify adsorbed molecules, processes that are exploited, for example, in heterogeneous catalysis and photochemistry. Here we report an effect of general importance that governs the bonding, structure formation and dissociation of molecules on oxidic substrates. For a specific example, methanol adsorbed on the rutile TiO2(110) single crystal surface, we demonstrate by using a combination of experimental and theoretical techniques that strongly bonding adsorbates can lift surface relaxations beyond their adsorption site, which leads to a sig- nificant substrate-mediated interaction between adsorbates. The result is a complex super- structure consisting of pairs of methanol molecules and unoccupied adsorption sites. Infrared spectroscopy reveals that the paired methanol molecules remain intact and do not depro- tonate on the defect-free terraces of the rutile TiO2(110) surface.