Automatically segmenting brain magnetic resonance images into grey matter, white matter, and cerebrospinal fluid compartments is a fundamentally important neuroimaging problem whose difficulty is heightened in the presence of aging and neurodegenerative disease. Current methods overlap greatly in terms of identifiable algorithmic components, and the impact of specific components on performance is generally unclear in important real-world scenarios involving serial scanning, multiple scanners, and neurodegenerative disease. Therefore we evaluated the impact that one such component, the Markov Random Field (MRF) optimizer that encourages spatially-smooth tissue labelings, has on brain tissue segmentation performance. Two challenging elderly data sets were used to test segmentation consistency across scanners and biological plausibility of tissue change estimates; and a simulated young brain data set was used to test accuracy against ground truth. Belief propagation (BP) and graph cuts (GC), used as the MRF optimizer component of a standardized segmentation system, provide high segmentation performance on aggregate that is competitive with end-to-end systems provided by SPM and FSL (FAST) as well as the more traditional MRF optimizer iterated conditional modes (ICM). However, the relative performance of each method varied strongly by performance criterion and differed between young and old brains. The findings emphasize the unique difficulties involved in segmenting the aging brain, and suggest that optimal algorithm components may depend in part on performance criteria.