Format compliance, a desirable feature of multimedia security systems, means that the secured bitstream resembles the unprotected compressed bitstream. It is called full format compliance, if the scrambled stream can be decoded by a typical decoder. In this paper, we address the issues that are to be carefully taken into account to develop efficient fully format compliant scrambling methods for compressed video. We also propose new selective scrambling methods for securing compressed video streams. The security issues, in different parts of these scrambling methods, are analyzed and their impact on bit-rate and complexity is discussed. We show that our scrambling methods provide significantly higher security and full format compliance, while having less impact on bit-rate and encoding/decoding complexity, as compared to existing semi-format compliant scrambling methods. The proposed techniques are integrated into the baseline mode of H.263 low bit-rate video coding standard.