PureMVC для C # не содержит порт для Windows Phone 7. (Страница, на которую вы указали ссылку, не отображает ее в качестве поддерживаемой платформы.) Это кажется хорошим объяснением того, почему он не использует NavigationService.
Если вы хотите использовать PureMVC, вам, скорее всего, придется самостоятельно портировать его на WP7 или дождаться выпуска версии для вас. Только вы можете решить, хотите ли вы идти по этому маршруту.
Если вы решите взглянуть на MVVM, я бы порекомендовал очень популярный MVVM Light Toolkit.