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, identifying candidate reference frame(s) from the first searching, second searching for prediction references for remaining pixel blocks of the new frame, wherein the second searching is limited to the candidate reference frame(s), 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.