What's so perfect about perfectly inelastic collisions? 
Perfectly Inelastic collision is the case when two bodies that collide, move with the same velocity after the collision.
An Elastic collision is a collision in which both Kinetic Energy and Momentum is conserved.
An Inelastic collision is a collision in which Momentum is conserved, but Kinetic Energy isn't.

We say that this specific case of Inelastic collision where both bodies move with the same velocity afterwards, to be 'Perfectly Inelastic'.
But why? Is it because this is the case when the maximum amount of Kinetic Energy is lost by the system? Can't there be a case where both bodies just come to rest after the collision so that we can say this to be Perfectly Inelastic?
 A: 
Is it because this is the case when the maximum amount of kinetic energy is lost by the system? Can't there be a case where both bodies just come to rest after the collision so that we can say this to be perfectly inelastic?

Yes, a perfectly inelastic collision dissipates the maximum possible kinetic energy. (Note that if the initial momentum was nonzero, they can't both come to rest, as that would violate momentum conservation.)
To see that the maximum possible amount of kinetic energy is dissipated, note that it goes into thermal energy in the bodies, which is independent of reference frame. So if the maximum possible thermal energy is produced in one frame, it is produced in all frames.
Now consider the frame where the total momentum is zero. In a perfectly inelastic collision, all of the kinetic energy in this frame is dissipated, because the bodies end up at rest afterward. So clearly the maximum possible thermal energy is produced in this frame, and hence it is in all frames.
A: The two bodies cannot be rest in the original frame of reference as the momentum needs to get conserved. But as pointed out by Nuclear Wang they can come to rest if the frame of reference is changed in appropriate manner. 
And the two bodies stick together because the deformation at the point of impact remains such and isn't elastic at all. Hence the two bodies would not get separated and would thus remain at rest relative to each other. It implies from this fact that the maximum amount of kinetic energy is lost by the system and also it gets converted to the potential energy of the deformation in the bodies.
A: Note that there is no absolute definition of "at rest", it will depend on your frame of reference. In the frame of the combined object after an inelastic collision, it is at rest. In any other reference frame, it is not. Whether the combined object is at rest or not will depend entirely on your point of view.
In a perfectly inelastic collision, the bodies stick together and move with zero relative velocity. In any reference frame, the two bodies have the same velocity, and in the frame of the combined body, that velocity is zero. Any other situation that has a non-zero relative velocity between the bodies is not a perfectly inelastic collision. 
In a non-perfect inelastic collision, there is no reference frame where both objects have zero velocity and are "at rest". No matter what reference frame you pick, at least one of the objects will be moving. So in a way, your proposed definition of inelastic collisions actually just reiterates what an inelastic collision is - it is the only type of collision where both bodies come to rest in some particular reference frame. Imperfect inelastic collisions do not have both bodies come to rest in any reference frame.
In the reference frame of the combined body, it is at rest, so its kinetic energy is 0. Before the collision, at least one of the bodies was moving, so there was non-zero kinetic energy. The maximum possible kinetic energy loss has taken place in the inelastic collision - in the frame of the combined object, all of the kinetic energy has been dissipated. In other reference frames, the combined object will still have kinetic energy, but it's still the maximum possible loss.
