Some old games (duck tales comes to mind) just didn't care about the the time and always ran their physics/render loop as fast as possible, with a fixed time step. Later, games (Classic Unreal for instance) started to use the RDTSC instruction that came with the Pentium, which subsequently lead to problems on SMP systems and/or CPUs with power saving features, due to a non-constant tick rate. I suspect Mech Warror 3 also uses it. Microsoft "fixed" that by introducing the QueryPerformanceCounter() API. Funnily enough, because a cheap high frequency time counter is also very valuable to OS developers, the RDTSC instruction now no longer returns the number of clocks but is a constant rate counter and old games work again, especially if the OS takes care to somewhat synchronize the TSC across all CPUs.
It seems timekeeping is still very much in a state of flux, with several timers available to choose from: 8253 timer, ACPI timer, LAPIC timers (per cpu), HPET timers and finally TSCs on each core, each with their own drawbacks.
> UpdatePhysics( elapsedTime );
IMHO the biggest problem with that is that it leads to jitter in the animation because it is impossible to determine in advance how much time you will spend rendering the subsequent frame/when the frame will actually be displayed (unless V-sync is turned off, then it becomes slightly easier). I don't think replays or synchronization between multiple computers are compelling arguments for fixed rate physics simulations, because running your physics simulation in lockstep with the server is basically impossible (and unnecessary IMHO); for replays all that is required is a log of all important events with an associated timestamp. I remember some multiplayer games from the past who did fixed step simulations and they all sucked because they limited the speed to the slowest computer. It is much better to have the server (fast computer) run an accurate simulation and the slow client to run an inaccurate simulation which is corrected frequently by updates from the server.
I'm also not entirely convinced by your examples. In my experience, exploding physics mainly happen if there is an unexpected delay between simulation steps. It looks to me like your simulation isn't properly damping the springs, or the time-step size is exceptionally jittery, but I could be wrong of course.