For motion-adaptive video retiming methods, the quest to lower the implementation complexity and improve the quality of motion estimation algorithms still continues. Comparing different motion estimators (MEs) and/or fine-tuning ME parameters is a time-consuming task, and it is even more demanding to identify the MEs with a robust performance among all the well-performing MEs. Therefore, a computer-aided design methodology is required to effectively explore the large design space. Such a methodology requires objective performance metrics. As it is hard to find perfect metrics, we present a design methodology that can use suboptimal measures and still identify robust MEs. The proposed methodology is demonstrated using two different MEs.