The statistics of velocity differences between pairs of heavy inertial point particles suspended in an incompressible turbulent flow is studied and found to be extremely intermittent. The problem is particularly relevant to the estimation of the efficiency of collisions among heavy particles in turbulence. We found that when particles are separated by distances within the dissipative subrange, the competition between regions with quiet regular velocity distributions and regions where very close particles have very different velocities (caustics) leads to a quasi bi-fractal behaviour of the particle velocity structure functions. Contrastingly, we show that for particles separated by inertial-range distances, the velocity-difference statistics can be characterized in terms of a local roughness exponent, which is a function of the scale-dependent particle Stokes number only. Results are obtained from high-resolution direct numerical simulations up to 20483 collocation points and with millions of particles for each Stokes number.