If atoms never "physically" touch each other, then how does matter-antimatter annihilation happen?

You should not think a particle as point like. Classically, the probability of two point like particles colliding with random location and velocity is 0, that is why you said it never happens.

However, at quantum mechanical level, these particle are described by wavefunction. It means that there is spreading in its spatial location, say 0.1nm (the minimum spreading is guaranteed by Heisenberg's uncertainty principle). The probability of annihilation can therefore be calculated by the overlap of these wavefunction and their interaction. This overlap is the meaning of "touching" in some sense.

When one is in the micro level of particles one has to stop thinking classically, i.e. with terms we have developed from our macroscopic observations.

"Touch" at the particle level can be defined as "interaction". Our feeling of touch actually does involve the electromagnetic interactions, we touch with the field of the molecules in our hand the field of the other objects, and this touching involves the exchange of force carrying virtual particles, i.e. particles which do not have definite mass but retain their quantum numbers characterizing them.

There is a precise mathematical description given graphically by the Feynman diagrams:

The diagram translates one to one with integrals that give the probability of this interaction happening. The exchanged electron in this diagram( or positron, depending on how one reads this) is virtual, it does not have definite mass.

Then the closer the e+ and e- are to each other the larger the probability that the scattering will result to an annihilation. So annihilation happens according to the probability of interaction.There are higher order exchanges but they give much smaller probabilities.