What are the properties of two bodies for their collision to be elastic? For example, must the shock wave in each body be of a particular form which influences the shape and material properties of the bodies?
I suspect part of the the answer is that the objects must be spherical, and the round-trip of the shock wave in each body must be the same, but this is just a guess.
 A: For a collision to be elastic, by the usual definition, no internal degrees of freedom of the colliding bodies can be excited/de-excited by the collision.
The internal degrees of freedom that might change in a collision include vibration, rotation (although some might argue about this), electron orbitals, electron spin, nuclear spin, etc. etc. etc.
For macroscopic objects, the density of states for all these parameters is so high that in practice it is astronomically unlikely that a TRULY inelastic collision will ever occur.  This is true even if the bodies are spherical, and have the same shock wave round-trip times, etc. etc.  The energy "lost" in a collision may be so small that it is extremely difficult to measure, but any collision of macroscopic objects is sure to be inelastic.
The situation is very different if the colliding particles are single atoms.  There, the density of internal states is so low (and coupling to various degrees of freedom so weak in the scattering) that it can be thousands of times more likely to have an elastic collision than an inelastic one.
Diatomic molecules are appreciably worse than atoms; it is relatively easy to excite/de-excite rotational motion of the molecule in a collision.  Inelastic collisions are about as common as elastic collisions.
Where's the tipping point?  By the time you've got something as big as, say, a virus, I'm sure it's extremely improbable to have elastic collisions.  But for something like a buckyball?  I have no idea.
A: Extended reply to Anonymous Coward:
Perfect, I'll argue that gaining rotation in a collision doesn't make it inelastic.  The kinetic energy is still there, it's just in the form of rotational kinetic energy.  But yes, that is strictly semantics.  You pretty much covered the question.
Generally I would claim that no macro objects can collide fully elastically but elementary particles can.  Of course, elementary particles only do so in the absence of an interaction and the "collision" is though a force like Coulomb repulsion.  Molecules, atoms, and other things can blur the line by having a meaningful chance of colliding fully elastically as well as a meaningful chance of some energy conversion taking place with kinetic energy.  Like nuclear cross sections, it is possible to provide numeric quantification of the probabilities of different interaction types.
For fun consider an equilibrium gas.  Collisions should be on average net-zero kinetic energy $\Delta$ but it's possible that collisions frequently (almost always even) convert binding energy or some other internal stored energy into kinetic energy.  I imagine this would be the case for gases with a large molecule size, it could even be of relevance to a chemist.
