The hierarchical subdivision strategy which decomposes a non-rigid matching problem into numerous local rigid transformations is a very common approach in image registration. While mutual information (MI) has proven to be a very robust and reliable similarity measure for intensity-based matching of multi-modal images, numerous problems have to be faced if it is applied to small-sized images, compromising its usefulness for such subdivision schemes. We examine and explain the loss of MI?s statistical consistency along the hierarchical subdivision. Information theoretical measures are proposed to identify the problematic regions in order to overcome the MI drawbacks. This does not only improve the accuracy and robustness of the registration, but also can be used as a very efficient stopping criterion for the further subdivision of nodes in the hierarchy, which drastically reduces the computational cost of the entire registration procedure. Moreover, we present a new intensity mapping technique allowing to replace MI by more reliable measures for small patches. Integrated into the hierarchical framework, this mapping can locally transform the multi-modal images into an intermediate pseudo-modality. This intensity mapping uses the local joint intensity histograms of the coarsely registered sub-images and allows the use of the more robust and computationally more efficient cross-correlation coefficient (CC) for the matching at lower levels of the hierarchy.