The accurate and automated registration of multimodal remote sensing data is of fundamental importance for numerous emerging geospatial environmental and engineering applications. However, the registration of very large multimodal, multitemporal, with different spatial resolutions data is, still, an open matter. To this end, we propose a generic and automated registration framework based on Markov Random Fields (MRFs) and efficient linear programming. The discrete optimization setting along with the introduced data-specific energy terms form a modular approach with respect to the similarity criterion allowing to fully exploit the spectral properties of multimodal remote sensing datasets. The proposed approach was validated both qualitatively and quantitatively demonstrating its potentials on very large (more than 100M pixels) multitemporal remote sensing datasets. In particular, in terms of spatial accuracy the geometry of the optical and radar data has been recovered with displacement errors of less than 2 and 3 pixels, respectively. In terms of computational efficiency the optical data term can converge after 7-8 minutes, while the radar data term after less than 15 minutes.