The observed tightness of the mass discrepancy-acceleration relation (MDAR) poses a fine-tuning challenge to current models of galaxy formation. We propose that this relation could arise from collisional interactions between baryons and dark matter (DM) particles, without the need for modification of gravity or ad hoc feedback processes. We assume that these interactions satisfy the following three conditions: (i) the relaxation time of DM particles is comparable to the dynamical time in disk galaxies; (ii) DM exchanges energy with baryons due to elastic collisions; (iii) the product between the baryon-DM cross section and the typical energy exchanged in a collision is inversely proportional to the DM number density. We present an example of a particle physics model that gives a DM-baryon cross section with the desired density and velocity dependence. Direct detection constraints require our DM particles to be either very light ($m << m_b$) or very heavy ($m >> m_b$), corresponding respectively to heating and cooling of DM by baryons. In both cases, our mechanism applies and an equilibrium configuration can in principle be reached. Here, we focus on the heavy DM/cooling case as it is technically simpler. Under these assumptions, we find that rotationally-supported disk galaxies could naturally settle to equilibrium configurations satisfying a MDAR at all radii without invoking finely tuned feedback processes. We also discuss issues related to the small scale clumpiness of baryons, as well as predictions for pressure-supported systems. We argue in particular that galaxy clusters do not follow the MDAR despite being DM-dominated because they have not reached their equilibrium configuration. Finally, we revisit existing phenomenological, astrophysical and cosmological constraints on baryon-DM interactions in light of the unusual density dependence of the cross section.