Image registration is a ubiquitous technique in medical imaging. However, finding correspondences reliably between images is a difficult task since the registration problem is ill-posed and registration algorithms are only capable of finding local optima. This makes it challenging to find a suitable registration method and parametrization for a specific application. To alleviate such problems, multiple registrations can be fused which is typically done by weighted averaging, which is sensitive to outliers and can not guarantee that registrations improve. In contrast, in this work we present a Markov random field based technique which fuses registrations by explicitly minimizing local dissimilarities of deformed source and target image, while penalizing non-smooth deformations. We additionally propose a registration propagation technique which combines multiple registration hypotheses which are obtained from different indirect paths in a set of mutually registered images. Our fused registrations are experimentally shown to improve pair-wise correspondences in terms of average deformation error (ADE) and target registration error (TRE) as well as improving post-registration segmentation overlap.