I'd like to add two votes.
One for OmniOutliner for iPhone.
And the other for focusing on iPhone OmniFocus!
Please do both, but by all means, make the currently shipping product your first priority. I'm very happy with OF for iPhone so far. I've never really gotten off the ground with the Mac version -- even though it is much more powerful. Having my GTD system in my pocket at all times seems like it was the missing piece, because now I'm not only creating projects and tasks, but checking my lists for things to do, and getting things done!
And to be entirely honest, I think you guys did a much better job on the iPhone version than the full-blown desktop app. The UI is far more intuitive and less confusing, and I actually find myself pulling out the iPhone version even when I'm sitting at my desk. It's easier to use, it launches 10 times faster, and has all the same information.
But I would seriously love to have a general outliner as well.
I've been using Zenbe "Lists" on the iPhone so far. It's better than the basic "Notes" app, but not by much. You're limited to a single, flat list of lists, and only a single level of items (i.e. no grandchildren). You can rearrange list items, but at the top level the lists themselves are sorted alphabetically. At the very least, it does let me move list items up and down, but mostly all it does is make me wish I had an Omni tool for the same job.
That said, I've been thinking about lists and outlines on the iPhone, and I really don't think a full-scale version of OmniOutliner is going to work on such a small screen (not to mention within 128 MB of RAM). You'd have to rethink how you're going to present and edit attributes that apply to all rows (i.e. columns). And with all the (much-deserved) talk about replication and other advanced features in OO4, the gap between what a mobile device can and should do, and what the desktop version of OO4 is capable of, is only going to become greater.
So it seems to me that perhaps it shouldn't be called "OmniOutliner", or the name should at least have a modifier like "Pocket" or "Mobile". Whereas OmniFocus for iPhone manages to do most of what the desktop version can do, and supports syncing the data back and forth, I can't imagine getting near feature-parity in this case (to the point of at least being able to view documents that use features not editable on the mobile version).
So maybe...think small? Tabula rasa...what are the most essential elements of an outline? Which features of desktop OO would cripple the basic purpose of the product if they were missing? I don't know. You guys figure it out. I'll buy it.
In the meantime, I very much appreciate that your time is focused on OmniFocus, because it's quickly becoming a central part of how I plan everything.