Is it correct to say that it is theoretically impossible for perfect rigid bodies to exist? If perfect rigid bodies were to exist, then consider a scenario in which two rigid bodies of equal masses moving with velocities of equal magnitude but opposite in direction colliding against one another. During the collision, the velocities of both the masses will decrease and they will reach zero for both the bodies (as the net kinetic energy is zero). Since the bodies are rigid, there will be no compression which stores the kinetic energy, which would further accelerate the bodies in opposite directions (as in case of a normal elastic collision). Is it correct to say that the existence of perfect rigid bodies would violate conservation of energy, and hence they cannot exist?
 A: You are right. Perfectly rigid bodies are an idealization, like point particles or massless frictionless pulleys. They do not exist.
But they are useful. Plenty of objects exist that are so rigid that you cannot ordinarily tell the difference.
A perfectly rigid object would violate other laws as well. For example, if you pushed it on one side, the whole object would instantly begin to move. That is, the forces would have to be transmitted from the near side to the far side faster than light.
In a real object, rigidity is caused by atomic bonds, which are electromagnetic forces. Changes in electromagnetism cannot travel faster than light.
A: At least if you consider special relativity then perfectly rigid bodies are impossible. I'll give two arguments for this namely finite speed of light and relativity of simultaneity:

*

*Finite speed of light

In relativity information should not propagate faster than the speed of light because otherwise it would travel back in time in some inertial frames (which might violate causality). When a moving body hits an obstacle its front should presumably change velocity as soon as it meets the obstacle but the rear should continue until that information has propagated to it at the speed of light at the fastest. Thus the body should deform.


*Relativity of simultaneity

What if we assume the body has exotic properties such that it can propagate information faster than light? It turns out that the body still can't be perfectly rigid in all inertial frames due to the relativity of simultaneity. If we assume that all parts of the body change velocity simultaneously in some inertial frame then they happen at different in another frame meaning in that in other inertial frames the body deforms.
Let's take an example. Assume that a rigid body bounces from a stationary wall and all parts of the body change velocity at the same time in this stationary (relative to the wall) frame.
First, look at the situation in the frame of the body before the collision. In that frame the body is not Lorentz contracted before the collision but is after it. Thus in that frame the front of the body changes velocity first and the body contracts in the collision.
Second, look at the situation in the frame of the body after the collision. In that frame the body is Lorentz contracted before the collision but isn't after it. Thus in that frame the rear of the body changes velocity first(!) before the front body has touched the wall and the body stretches(!) in the collision.
A: 
Since the bodies are rigid, there will be no compression which stores the kinetic energy, which would further accelerate the bodies in opposite directions (as in case of a normal elastic collision).

Rigidity disallows compression for each body separately, but the two-body set is not rigid. The energy may be stored by compressing the set as a whole.
E.g. imagine each body as a rigid cloud of particles. Imagine interaction where the more one cloud submerges into the other, the larger a repulsive force between them. The force will decelerate the clouds, then accelerate in opposite directions; a collision will occur. Note in this model there is no need for infinite force or infinite acceleration, each collision takes some time like in a model where bodies get compressed.
Similarly you can bounce two bodies with equal electric charge off each other, or bounce a magnet off another magnet (if you can prevent them from reorienting). In theory the bodies or the magnets may be perfectly rigid, the kinetic energy transforms into potential energy (and back) accumulated in the interaction between the two bodies, not inside each body separately.
Perfectly rigid bodies are impossible under special relativity (and some answers address this), but in the classical mechanics there is no fundamental problem with them. For our cloud of particles to be rigid, there must be instantaneous forces between the particles (internal forces), depending not on the relative positions of the particles but on external forces; so if you exert a force on one particle, each particle instantly gets its share and the whole cloud accelerates uniformly. Even before special relativity physicists realized this is not what happens. Still such internal forces (and thus perfectly rigid bodies) don't violate Newton's laws.

Is it correct to say that the existence of perfect rigid bodies would violate conservation of energy, and hence they cannot exist?

No. Or rather: if the existence of perfect rigid bodies violated conservation of energy somehow, it wouldn't be because of what you described in the question.
A: You are correct that there are no perfectly rigid bodies, but your "proof" is flawed. You posit that "during" the collision, the velocity of both objects is zero. That implies that the zero-velocity state lasts for a finite amount of time.  If the bodies were indeed totally rigid, the "collision" would be instantaneous.  At that point, the velocities are not zero, they are undefined.  (The concept of instantaneous velocity is a limit of Newtonian calculus as the time step tends to zero; but if the time is exactly zero, it is still undefined!)  Having undefined velocities for an instantaneous point in time does not create an impossible condition.
A: There is a nice answer by @mmesser314 and @quantumwiz I would like to add an interesting note to the list of violations of the laws of physics.
The body in your example should in our universe ultimately be made of quarks and electrons, building up protons, neutrons, and atoms and eventually the molecules that build up your objects. These are bound by the strong and EM force including the covalent bonds that hold the object and give it its supposed ultimate rigidity. Now these forces are strong, but not infinitely strong, because we happen to live in a universe where conservation of laws hold (verified as per our experiments). Now if these forces are not infinitely strong, if you apply enough energy (heat up etc.), first the covalent bonds between your objects' molecules will change (break), and the object will have to lose its rigidity.
Having a perfectly rigid object would not only violate as you see from the other answers causality and SR (faster then speed of light information transfer), but it would have to violate the laws of quantum mechanics that include the governance of covalent bonds, not to mention the strong and EM force (as we understand it) in all.
We happen to live in a world where the universe dictates that the rules are ultimately quantum mechanical and these laws are incompatible (from the very building blocks) with a perfectly rigid body.
A: Not quite.  You are correct that rigid bodies do not exist, but this is not the reason.  Your assumptions imply that for a velocity to go from a positive value to a negative value, it must go through 0.  However, it is also possible for velocity to be discontinuous.  You can have a velocity function that is defined to be "-5 for all times less than 0, +5 for all times equal or greater than 0".
What you have done is show that, for rigid bodies to exist, it must be possible for velocity to be discontinuous.  That is the only way to support the conservation laws we know in the presence of rigid bodies.
Now we do find that velocities are continuous in practice.  This extra statement is required before we can prove that rigid bodies are impossible.  And, actually, a second statement is required which is to prove that it is physically possible to reach a configuration like you describe.  This may seem like an absurd subtlety, given how obvious it is that you can set two such objects in motion, but its an important part of the proof.  Physicists love to hide pesky discontinuities behind configurations that can never possibly happen!
A: If perfect rigid bodies were to exist, there would be an infinite pressure acting on a perfect rigid flat table when a perfect rigid ball is placed on top of it. The area of the contact surface is zero.
$$
p = \frac{W}{0} = \infty
$$
A: 
Is it correct to say that the existence of perfect rigid bodies would violate conservation of energy, and hence they cannot exist?

I think that conclusion cannot be drowned. For a perfect rigid body of mass $m$ the impulse conservation $$m v_{1}+m v_{2}=0~\implies~v_{2}=-v_{1} \tag{1}$$ and energy conservation laws $$\frac{1}{2}m v_{1}^2+\frac{1}{2}m v_{2}^2=E=const.=m v_{1}^2 \tag{2}.$$
are fulfilled at all times.
Whether perfect rigid bodies exist is an another question which has been already answered by others here. A perfect rigid body, or a perfect fluid, is an idealization (limiting case) for low velocities in comparison to light or sound velocities, respectively.
A: It would violate energy conservation laws so no, but at this point it would have to be a thought excersise alone. Diamond being our hardest known structure to date in its strongest most bonded linear form would have to be the medium so it would clearly be a no. All mental gymnastics and excersises have also given the same answer having to suppose it only possible in a single "frozen frame" with other violatory properties such as instantaneous information exchange having to simultaneously exist. Maybe in the future but at this point in our scientific evolution it would be a no.  Maybe the rigidity of sub atomic quantum particles would prove your assertion correct in the future but the cost alone would  be astronomical compared to financial recompense thus making it untenable and therefore make it an excersise in futility. Its a no from me friend you're correct
A: You don't even need special relativity to understand why the statement "Perfect rigid bodies are impossible" is correct. Just some structural engineering.
Imagine you have a 100 m long rigid board of mass 100 kg with g = 10 m/s^2 laying horizontally on 3 pillars. One at 0 m, one at 50 m, and one at 100 m. What force is each pillar exerting on the motionless board?
The total force due to gravity is 1000 N so we know $F_1 + F_2 + F_3 = 1000 N$. We also know there is no net torque on the board. Let's consider the torque about the center of mass which happens to be where the center pillar is located. The torque from the center pillar and gravity are both 0 Nm since they act at the pivot. The torques from the two outer pillars must be equal and opposite so $F_1 = F3$.
\begin{align}
F_1 + F_2 + F_3 =& 1000 N\\
F_1 - F_3 =& 0 N
\end{align}
But we have no other equations. We have two equations and three unknowns. This means that the physical system is underconstrained. For example, we might have $F_1 = F_3 = 500 N$ and $F_2 = 0 N$ or $F_1 = F_3 = 0 N$ and $F_2 = 1000 N$. Both of these are consistent solutions to the statics problem.
But if you build such a structure there WILL be answer. How is the answer determined? How is this problem/paradox resolved? The answer is that the rigid body assumption must be relaxed.
As a first step we can continue to treat the board as a rigid body but permit that the pillars must be compliant meaning that they deform under load like a spring. As they are compressed they exert a compression force on whatever is compressing them. To first order the force is linear in the magnitude of the compression, like Hooke's law.
We now have the same two equations as above but we have additional equations:
\begin{align}
F_1 =& k_1 x_1\\
F_2 =& k_2 x_2\\
F_3 =& k_3 x_3\\
\end{align}
We've added 3 equations and 3 unknowns so the problem is still under constrained. But, we assumed the board is rigid. This means that $x_1, x_2$ and $x_3$ must be linear to ensure the board is in contact with all 3 pillars.
\begin{align}
x_1 =& s (0 m) + b\\
x_2 =& s (50 m) + b\\
x_3 =& s (100 m) + b
\end{align}
Here I've added 2 more variables, $s$, the slope or slant of the board, and $b$ the vertical offset of the board. We now have 8 equations and 8 unknowns and a constrained problem.
I won't actually solve this, but it is not to hard to see that if $k_1 = k_2 = k_3$ then $x_1 = x_2 = x_3$ with $F_1 = F_2 = F_3 = 1000 N / 3$ is a solution to the problem. If the spring constants are not all equal then the solution will depend on the relative compliances of the three pillars.
What if you have $N$ pillars? In that case you have $N$ unknown forces and $N$ unknown displacements. The net force and net torque equations give you 2 equations. The Hooke's laws give you $N$ equations. The linear "shape" constraint on the rigid board leaves us with $N$ new equations and 2 new unknowns for a total of $N + N + 2$ unknowns and $N + N + 2$ equations, so the problem is always constrained.
In real life the board itself cannot be rigid and must also be treated as a mass/spring system that can deform in shape, and this deformation will lead to compression and tension that adds to internal forces within the system that must be taken into account for accurate modeling.
A: The thought experiment in the OP is a valid one to consider whether rigid bodies can exist or not, but the analysis/conclusion aren't totally right.. Suppose we have two objects mass of mass $m$ moving towards each other at velocity $v$. It is clear to see from conservation of energy and momentum that after the collision the two bodies will be moving away from each other at velocity $v$. So this question actually poses no problem for conservation of momentum and energy.
The problem comes when you ask the question: What is the velocity over time for each body? The answer is that the at the moment of collision the bodies instantaneously reverse their velocity from $\pm v$ to $\mp v$. This would require an infinite force and therefor an infinite acceleration. We typically consider discontinuities like this to be unphysical. This is the paradox and why rigid bodies are impossible in theory.
To better model this situation each of the bodies should be treated as a spring that can compress. Then when the two bodies approach and eventually touch each other the springs will compress, slowing down, and eventually reversing the direction of the two objects over time. In this case you will find the velocity profile of each body to be continuous* in time. The collision will take a finite amount of time but the end result will be the same.
*The profile will be continuous but the derivative of acceleration, jerk, will be discontinuous at the moments the springs touch and release from each others. To solve this discontinuity you would need to model the fact that the interactions between the two bodies actually arise from long-range electromagnetic forces, meaning that even when the masses are far apart there is a tiny force already acting between them. This force (related to Pauli exclusion even) is highly non-linear, so it only becomes significant when the masses are close, but the fact that it is non-zero at long range is what saves us from this final discontinuity.
In conclusion: The OP's thought experiment does disprove the existence of rigid bodies, but not because of energy conservation. The reason is because forces/accelerations must be finite, or equivalently, physical properties must be continuous in time.
A: 
Is it correct to say that it is theoretically impossible for perfect rigid bodies to exist?

No, it is not correct to say that.
There is a ceramic mug on my table right now. I am certain, that if I throw it with enough force against a solid wall, the mug would break (to the point that there would be no ceramic mug anymore). However, this certainty does not make me doubt the existence of ceramic mugs in general or this mug in particular. And if in the future this specific ceramic mug does break, this would not mean that it would be wiped from existence retroactively, nor would it mean that other ceramic mugs would stop existing.
Similarly, OP's argument as well as all the answers asserting that perfect rigid bodies do not exist, because of various scenarios involving such rigid bodies which lead to violation of some fundamental laws, all have the same fallacy. When perfectly rigid bodies are placed in such scenarios they stop existing as perfectly rigid bodies at that moment in that place, but this does not mean that perfectly rigid bodies did not exist before or would not exist in the future or in other places.
So to iterate:

*

*two perfectly rigid bodies do not collide with each other;

*there is no sound in perfectly rigid bodies;

*perfectly rigid body does not change its state of rotation; …  etc.
There are no contradictions in such statements.
So we might as well conclude that perfectly rigid bodies can exist, there is no internal contradiction in the notion.
