I ran into just such a situation for a client and while I”m also not a fan of left hand navigation it was the decision of the client to utilize it in conjunction with their top navigation, and in retrospect it made sense for them. To keep things easily navigable we also implemented breadcrumbs (which is a good practice anyway).
The mission was to display sub-pages of the current page you are on in the left nav and once you hit the bottom of the hierarchy to show pages which are parallel to that page within the same branch of the hierarchy.
After some digging and experimentation I came up with the following which executes perfectly in only a few lines of code.
$children = wp_list_pages("title_li=&child_of=".$post->ID."&echo=0&depth=1");
if ($children == "")
$children = wp_list_pages("title_li=&child_of=".$post->post_parent."&echo=0&depth=1");
<?php echo $children; ?>
<?php endif; ?>
Of course you style to taste…
That’s it! Used in conjunction with a standard WordPress top-navigation and breadcrumbs you can easily display page sensitive multi-level navigation for your super-complex multi-level site!