The invention is related to methods and apparatus that decode robustly encoded video bitstreams. One embodiment of a decoder can advantageously reconstruct a predictive-coded video object plane (P-VOP) from a standard motion vector and the previous frame; from a redundant motion vector and a frame prior to the previous frame; or from both. Advantageously, this permits the decoder to display a frame based on a reconstructed VOP in the presence of unfavorable environmental conditions, such as interference, delays, and the like, which could otherwise corrupt a previous frame that is used as a reference by a standard decoder, such as a standard MPEG-4 decoder. One embodiment is advantageously backwards compatible with standard MPEG-4 compliant bitstreams and retrieves redundant motion vector information from user data video packets. One embodiment includes at least one extra frame buffer or memory, which stores a reference frame corresponding to a redundant motion vector.