I finally asked Apple Technical support the same question. They concluded that this was a bug in iOS, so I have filed a bug report to Apple. The same bug seems to appear in iOS 6 and in the latest iOS 7 (Beta 5).
Apple Technical Support suggested the following:
As a workaround, you can move your cleanup code to a separate method which the AppDelegate would then invoke on the navigation controller's top view controller, before it pops the entire navigation stack.
However, I think this exposes too much of my details in the view controller, so I chose to implement it using willMoveToParentViewController:
instead. This method is called when the view controller is removed from its parent, and it is called properly.