1. A video coding method, comprising: when a new frame is presented for coding, identifying from among pixel blocks of the new frame a plurality of complex pixel blocks, first searching for prediction references for the complex pixel blocks from among a plurality of reference frames, second searching for prediction references for remaining pixel blocks of the new frame, wherein the second searching is limited to reference frame(s) that are prediction references of the complex pixel blocks, and coding complex pixel blocks and non-complex pixel blocks of the new frame according to predictive coding techniques using prediction references identified in the first and second searches.