The description seems to ignore elastic collision - contact always occurs on a frame boundary which is noticeable wrong when higher velocities occur. Wouldn't the described solution result in 'sticking'?
No, because the rebound velocity doesn't depend on how far two bodies intersect.
To answer the wider question - when a contact is detected, you can immediately calculate the new velocity of the two bodies. Then you move things around to be nonintersecting. Then next frame, everything has the correct velocity.
(In fact, this will be done in two passes. Collision detection will generate a list of contacts, containing properties like the initial velocities of the two bodies. Then the collision resolution phase will change the velocities.)
