Пройдя поиск более недели, я наконец нашел, как сделать эту работу правильно. Оказывается, DataTemplates не слишком хорошо работают для динамических меню. Правильный способ сделать это - использовать свойство ItemContainerStyle объекта MenuItem. (Или это ItemStyleContainer?)
Просто создайте стиль, чтобы переопределить заголовок и установить его на то, что вам нужно. Я переопределил ItemsSource, чтобы включить моих детей. Однако будьте осторожны, так как дети наследуют стиль, и у каждого из них одни и те же дети, и генерируется рекурсивное меню. Вам нужно переопределить ItemsSource ваших детей и установить для него пустой x: Array или лайки.
Есть несколько блогов, описывающих, как использовать ItemContainerStyle, ознакомьтесь с ними.