Also, could the closing velocity or some other parameter come into effect?
According to Wikipedia,
in a series of experiments performed at Florida State University in 1955, it was shown that the COR varies as the collision speed approaches zero, first rising significantly as the speed drops, then dropping significantly as the speed drops to about 1 cm/s and again as the collision speed approaches zero.
Sadly the link to the paper on this is dead.
To answer the main question, Cholesky's suggestion of a table is a good one, but if you want to reduce the number of cases you have to select values for then one approach would be to store for each material a base restitution and a weight with which to take a weighted average. What restitution is really about is how much of the energy of the collision is converted into forms other than the post-collision kinetic energy of the bodies. Sound can be neglected: what you're interested in is deformation. So give easily deformed materials such as soft sand a high weight and a low restitution and you have a model which should be good enough.
After all, games only have to feel right to the player: they don't have to be accurate simulations of the real world.