These two links are good reading:http://www.niksula.hut.fi/~hkankaan/Hom ... avity.htmlhttp://gafferongames.com/game-physics/f ... -timestep/
What I'm currently using is a slightly modified version of the Gaffer on Games article - I don't bother with handling the less than 72 fps case (a few things get simpler this way and I run so fast that it rarely happens anyway). This has evolved another step or two in as-yet unreleased code - there, Host_Frame never returns early and both client and server events are based on a time elapsed since they last ran. That fixes up some instability problems encountered on some machines where sometimes two server timeslices would pass before running.
My theory is that 72 fps was chosen because it was the common refresh rate on old CRT monitors at the time. Just like modern games tend to lock at 60 fps (or some multiple) - no other reason, really.
I'm with Metl that 72 fps shouldn't be considered "optimal" - there's an Abrash talk from 1996/97 where he makes mention of "40 fps at 640 x 480" so I use that as a ballpark guideline. I'd actually prefer to run my physics at around this rate, or maybe a little higher (40 or 50 divide nice and evenly into 1000 too, which helps a lot with millisecond timers), but I'm aware of the general assumption that it runs at 72 so don't want to deviate from that.
I highly doubt that Quake was seriously tested at anything above 50 fps back in 1996 - especially so because the original physics was designed on a software renderer which ran like mud for such a long time during development.
It's interesting that older versions of Direct 3D (9 and before) had a D3DPRESENT_DONOTWAIT flag, which in theory would return immediately if the hardware was waiting on a vsync interval, so you could do some useful work (or just yield the CPU) during that time period. It was supposed to be supported by AMD/ATI but I never got to test it; it definitely never worked on NVIDIA so I never really bothered with pursuing it any further. It would have been good for running physics at 72 fps with vsync enabled though.
I'd add a multiple of your mouse polling rate to the conditions that Spike mentioned.