No, that's more or less what I'm thinking. Of course a list is just a boring tree, so I suppose if one wanted to handle all possible navigation styles with a single service contract then returning a tree might be the thing to do.
In reality, though, if you have tabbed or pulldown navigation this generally *augments* rather than replaces the breadcrumb navigation bar.
And things like pulldown navigation menus tend not to depend on the page itself but rather ... the subsite, maybe? So a way to build navigation menus and pass them to a master template would be useful but wouldn't need to be constructed by every package and page, would it? It could be generated by (say) tha subsite's master template script.
In which case the separate context bar concept remains a list always.