A video encoder and corresponding methods are provided for selecting the mode of a current macroblock of an inter-coded frame, including one or more of checking first modes for a subset of macroblock modes, selectively checking other modes in response to motion vector information of the checked first modes, and selecting the mode for the current macroblock in response to the checked modes; checking the macroblock mode of at least one neighboring macroblock, and selecting the mode for the current macroblock in response to the macroblock mode of the at least one checked neighboring macroblock; checking the cost of a subset of macroblock modes, further checking only intra-coded modes if the checked cost meets a preset criteria, and selecting the mode for the current macroblock in response to the checked modes; and adjusting an early-stopping threshold in response to checked macroblock modes, and selecting the mode for the current macroblock in response to the checked macroblock modes if the adjusted early-stopping threshold is met.