App design: UITabBarController within UINavigationController

Question

I have a very specific application design that I'm trying to figure out how to create with iOS 4.

Here's how it works:

1. The user selects an installed data set, or triggers a data set download.
2. The user provides a key for decrypting the data set.
3. A tab bar is shown with different search options for looking at the data. There are more searches than fit on the tab bar, so there's a More item and an Edit button. (Thanks, Apple!)
4. The searches provide different options, some requiring an additional screen for setup.
5. Once a search result is tapped, the user sees details. They can usually tap deeper into the result.
6. The tab bar stays visible as users look at details, letting them start a different kind of search. Tapping a search takes them back to step 3.
7. If at any time the device goes to sleep, the data must be locked. This is a hard requirement, despite may efforts to remove it. So at the moment, I'm returning to step 2.

I've implemented this in iPhone OS 3.1 with a UINavigationController for steps 1 and 2. The app pushes a UITabBarController with each tab represented by a UINavigationController for step 3, hiding the navigation on the outer controller. The user then operates within this UITabBarController. For a lock, I just pop the tab controller off the navigation controller.

It mostly works in iPhone OS 3.1, but it's fragile and hackish. There was no good way to change the data set, but the user could just close the app. With iOS 4 this workaround is gone! The only option I see is returning to step 2 on a supsend/resume, which is going to be a terrible multitasking experience.

How should I be doing this?

1. The tabs don't make sense until the data set is opened and unlocked.
2. I (and my users) really like the single tap (no matter the depth) to start a new search.