Лучшим решением будет использование строки запроса вместо обмена сообщениями. Если вы не используете строку запроса, вам придется иметь дело с такими ситуациями, как приложение деактивируется (tomestoned), затем пользователь нажимает «назад», и ваше приложение загружает вторую страницу без получения сообщения.
Однако, если вы хотите продолжить по этому пути, вы можете изменить свой ViewModelLocator таким образом, чтобы ViewModel вашей страницы создавался немедленно (например, в ctor), а не по мере необходимости. Поскольку ViewModelLocator создается сразу после загрузки вашего App.xaml, вы знаете, что любые модели представлений будут созданы немедленно. Пока ваша модель представления регистрируется для сообщений в своем конструкторе, она должна получать сообщение.