Methods and apparatus that allow encoding of video data in pipelined encoder architectures with reduced encoding performance penalty. The methods and apparatus encode video data without the need to flush the data pipeline and re-encode macroblocks, thus saving time and resulting in an increase in the encoder's throughput. In one embodiment, macroblocks are encoded in a data pipeline to form a first video slice of a plurality of video slices. Once a macroblock overshoot condition occurs, the overshooting macroblock is determined and a second video slice is formed that includes at least one of the overshooting macroblock and the encoded macroblocks without re-encoding the included overshooting macroblock and encoded macroblocks. For example, a second video slice may be formed from the overshooting macroblock, and any remaining encoded macroblocks, that do not form the first video slice.