Dynamic contrast-enhanced magnetic resonance (DCE-MR) imaging can be used to study microvascular structure in vivo by monitoring the abundance of an injected diffusible contrast agent over time. The resulting spatially resolved intensity-time curves are usually interpreted in terms of kinetic parameters obtained by fitting a pharmacokinetic model to the observed data. Least squares estimates of the highly nonlinear model parameters, however, can exhibit high variance and can be severely biased. As a remedy, we bring to bear spatial prior knowledge by means of a generalized Gaussian Markov random field (GGMRF). By using information from neighboring voxels and computing the maximum a posteriori solution for entire parameter maps at once, both bias and variance of the parameter estimates can be reduced thus leading to smaller root mean square error (RMSE). Since the number of variables gets very big for common image resolutions, sparse solvers have to be employed. To this end, we propose a generalized iterated conditional modes (ICM) algorithm operating on blocks instead of sites which is shown to converge considerably faster than the conventional ICM algorithm. Results on simulated DCE-MR images show a clear reduction of RMSE and variance as well as, in some cases, reduced estimation bias. The mean residual bias (MRB) is reduced on the simulated data as well as for all 37 patients of a prostate DCE-MRI dataset. Using the proposed algorithm, average computation times only increase by a factor of 1.18 (871 ms per voxel) for a Gaussian prior and 1.51 (1.12 s per voxel) for an edge-preserving prior compared to the single voxel approach (740 ms per voxel).