It would appear that it’s not possible to override the OnBackKeyPress method to intercept the back key unless you use the Navigate method to move between pages in your application.
My previous method of navigation was to change the root visual, like:
App.Current.RootVisual = new MyPage();
This meant I could keep all my pages in memory so I didn’t need to cache the data stored on them (some of the data is collected over the net).
Now it seems I need to actually use the Navigate method on the page frame, which creates a new instance of the page I’m navigating to.
(App.Current.RootVisual as PhoneApplicationFrame).Navigate(
new Uri("/MyPage.xaml", UriKind.Relative));
Once I started navigating using this method, I could then override the back button handling in the way described in my question…