The normal max sync speed is the speed at which the 1st shutter curtain is wide open but before the 2nd curtain starts to closed. On the 1DmkII, that is 1/250th of a second. At higher shutter speeds, the sensor is not fully exposed when the 1st and 2nd curtains are travelling. So, at 1/500, the 2nd curtain start its travel when the 1st curtain is still making it's way to the other end of the frame. What this means is that, if a flash were to go off when the 2nd curtain starts its travel, only a portion of the frame is exposed by the flash. The sync speed with the 1DmkII is a mechanical limitation as the shutter can only go so fast.
With the 1D which uses a CCD sensor, the shutter is controlled not just mechanically but also electronically by switching the sensor on and off at the appropriate time. That is how it is able to achieve a sync speed of 1/500 and a max shutter speed of 1/16000 using the same shutter mechanism as the 1DmkII. At 1/500 to 1/16000 shutter speeds, the 1D essentially uses the mechanical shutter speeds of 1/250 to 1/8000 and then just turns off the CCD sensor at the right time to get the effective faster shutter speed.
To use the flash at higher than the max sync speed of the camera, the flash has to be set to high-speed sync mode. In this mode, the flash will pulse the flash (at the appropriate frequency) for the entire duration that the shutter is traveling across the frame. This results in the frame being evenly exposed. However, the drawback is that the pulsing reduces the effective strength of the flash and the higher the shutter speed, the less power you get from the flash.