Consider the iPod.  The simple hierarchical drilldown UI popularized by the iPod is well suited to the small screens and limited input options on mobile devices.

If you wanted to create an open platform for building network powered applications based on this style of UI, what would be the best markup language to use?

One possibility would be to redefine the interpretations of subsets of XHTML– perhaps nested lists with the appropriate CSS attribute could be displayed using a drilldown UI, for example.

Another, perhaps better option is to use OPML, which already has a lot of the right semantics and is considerably more constrained that XHTML.  A link node could link to another OPML document, a traditional XHTML document, or perhaps to application specific behaviors that run on the client device.

In the case of Beyond411, things like yellow page category menus and categorized plugins could be expressed very naturally as OPML hierarchical menus.