The dynamics of dissipative soft-sphere gases obeys Newtons equation of motion which are commonly solved numerically by (force-based) Molecular Dynamics schemes. With the assumption of instantaneous, pairwise collisions, the simulation can be accelerated considerably using event-driven Molecular Dynamics, where the coefficient of restitution is derived from the interaction force between particles. Recently it was shown, however, that this approach may fail dramatically, that is, the obtained trajectories deviate significantly from the ones predicted by Newtons equations. In this paper, we generalize the concept of the coefficient of restitution and derive a numerical scheme which, in the case of dilute systems and frictionless interaction, allows us to perform highly efficient event-driven Molecular Dynamics simulations even for non-instantaneous collisions. We show that the particle trajectories predicted by the new scheme agree perfectly with the corresponding (force-based) Molecular Dynamics, except for a short transient period whose duration corresponds to the duration of the contact. Thus, the new algorithm solves Newtons equations of motion like force-based MD while preserving the advantages of event-driven simulations.