In this paper, we propose a new multi-scale technique for multi-modal image registration based on the alignment of selected gradient orientations of reduced uncertainty. We show how the registration robustness and accuracy can be improved by restricting the evaluation of gradient orientation alignment to locations where the uncertainty of fixed image gradient orientations is minimal, which we formally demonstrate correspond to locations of high gradient magnitude. We also embed a computationally efficient technique for estimating the gradient orientations of the transformed moving image (rather than resampling pixel intensities and recomputing image gradients). We have applied our method to different rigid multi-modal registration contexts. Our approach outperforms mutual information and other competing metrics in the context of rigid multi-modal brain registration, where we show sub-millimeter accuracy with cases obtained from the retrospective image registration evaluation project. Furthermore, our approach shows significant improvements over standard methods in the highly challenging clinical context of image guided neurosurgery, where we demonstrate misregistration of less than 2 mm with relation to expert selected landmarks for the registration of pre-operative brain magnetic resonance images to intra-operative ultrasound images.