Previous authors have considered optimal stopping problems driven by the running maximum of a spectrally negative Lévy process $X$, as well as of a one-dimensional diffusion. Many of the aforementioned results are either implicitly or explicitly dependent on Peskir's maximality principle. In this article, we are interested in understanding how some of the main ideas from these previous works can be brought into the setting of problems driven by the maximum of a class of Markov additive processes (more precisely Markov modulated Lévy processes). Similarly to previous works in the Lévy setting, the optimal stopping boundary is characterised by a system of ordinary first-order differential equations, one for each state of the modulating component of the Markov additive process. Moreover, whereas scale functions played an important role in the previously mentioned work, we work instead with scale matrices for Markov additive processes here. We exemplify our calculations in the setting of the Shepp-Shiryaev optimal stopping problem, as well as a family of capped maximum optimal stopping problems.