We propose a method for reliably and accurately identifying anatomical landmarks in 3D CT volumes based on dense matching of parts-based graphical models. Such a system can be used to establish reliable correspondences in medical images which can be useful on their own or as part of more complex processing e.g. atlas building. We propose and investigate novel methods for efficiently optimizing parameters of appearance models for landmark localization in 3D images. We also investigate the trade-off between the number of model parameters and registration accuracy. We present results for the localization of 22 landmarks in clinical 3D CT volumes of cancer patients and optimization of part-specific patch scales. Over-fitting is likely due to an intrinsically high variability of the data and a limited labeled training and test set, here 83 scans, so we employ a rigorous bootstrap analysis to validate the results. The average mean and maximum registration error over all landmarks is reduced by 31% and 25% for the optimized model, compared to an empirically determined baseline. Additionally, we show a significantly improved performance over standard methods as the number of free parameters increases from an isotropic patch scale shared by all parts, to specific anisotropic patch scales learnt for each part in the model.