Fast moving objects

not quite. Instead, the collision test is done using the swept vector (velocity of disaplcement of the object), as an integral part of the test. This returns the time of collision. In particular, Quake3 uses BSP trees and ray-tracing techniques to do the collision detection and compute the monet of impact. THen it moves the object (usually a bounding box) to that time, and slide / reflect the object on the normal. For player against players, I'm not 100% sure, but it probably uses the same technique, of sweeping the boxes against each other and finding the time of collision.

To reduce the number of call, you use broad phase culling (fancy word for 'sorting' collisions and minimise the number of tests).

Usually you use some sort of spatial data structure to minimize the number of object pairs you have to check.

One way is a 2d or 3d grid. Another is an octtree. This way you can quickly find objects nearby the current & future position of the moving object.

You also can choose not to handle > 1 collision per object per frame to speed things up. For instance, once you detect a real collision ( ienot a time == 0.0 collision like gravity for an object on a floor ), you may choose to only detect an simulate up to its first collision, update its velocity for next frame, and then go on to the next object.