"Flexi Pages Widget" are still one of the best flexi navigation!!
(in WP3+ world, too...)
But - could be possible in some way "override" the default WP horizontal navigation? That is - to have a user accessible Admin menu item, where you can declare one (or more) individual navigation bars, independently on built-in WP3+ Custom Post functionality? Based on Flexi Pages Widget or whatever else?