Invalid option selected. Recalculate shipping quotes to continue.

Yep, I agree with you completely. Let me walk you through my scenario:

1. Place products in cart
2. Go to checkout page with all checkout panes listed in the above-referenced posting in the order given. Shipping quotes pane occurs before delivery info pane.
3. Fill in ALL info for the order (billing info, delivery info, payment info, etc), and select a shipping option from the top pane before clicking the "Review Order" button. (Note we have now collected delivery information and successfully queried the server for quotes and selected a shipping option.)
4. BANG! "Invalid option selected" message appears. All info is filled in, and a valid option has been selected.
5. Rinse and repeat with alternate shipping method, same thing.
6. Repeat with a flat-rate method that does not require any delivery info and the "Review Order" page can be reached

On examining the order being processed after clicking "Review order" you will see that the panes are processed in the order that they are arranged to appear on the page via the checkout pane admin page. What this means is that if the shipping quote pane appears before the delivery info pane, the form validation function has no delivery information to pass to the quote pane's validation handler - the values with keys beginning with "delivery_" are not populated in the order object that is passed to all panes weighted to appear before the delivery info pane. Quotes fail, checkout validation fails, and our favorite error msg appears.

Switch the shipping quotes pane to be weighted to appear after the delivery info pane, and the order object passed to the quote pane validation hook has what it needs to fetch quotes.

This is not a "support request" but a "bug report" - if UC allows you to rearrange checkout panes, then the checkout validation logic should not hinge on what order the panes are arranged.

Here's the function in it's entirety that is causing the problem:

/**
 * @see uc_cart_checkout_form()
 */
function uc_cart_checkout_form_validate($form, &$form_state) {
  global $user;

  if (empty($_SESSION['cart_order'])) {
    $order = uc_order_new($user->uid);
    $_SESSION['cart_order'] = $order->order_id;
  }
  else {
    $order = new stdClass();
    $order->uid = $user->uid;
    $order->order_id = $_SESSION['cart_order'];
    $order->order_status = uc_order_state_default('in_checkout');
  }

  db_query("DELETE FROM {uc_order_products} WHERE order_id = %d", $order->order_id);
  $order->products = unserialize($form_state['values']['cart_contents']);

  $context = array(
    'revision' => 'original',
    'type' => 'order_product',
  );
  foreach ($order->products as $key => $item) {
    $price_info = array(
      'price' => $item->price,
      'qty' => $item->qty,
    );
    $context['subject'] = array(
      'order' => $order,
      'product' => $item,
      'node' => node_load($item->nid),
    );

    // Get the altered price per unit, as ordered products have a locked-in
    // price. Price altering rules may change over time, but the amount paid
    // by the customer does not after the fact.
    $price = uc_price($price_info, $context) / $item->qty;
    if ($order->products[$key]->price != $price) {
      $order->products[$key]->data['altered_price'] = $price;
    }
  }

  $order->order_total = uc_order_get_total($order, TRUE);

  // Validate/process the cart panes.  A FALSE value results in failed checkout.
  $_SESSION['checkout_valid'] = TRUE;
  foreach (element_children($form_state['values']['panes']) as $pane_id) {
    $func = _checkout_pane_data($pane_id, 'callback');
    if (is_string($func) && function_exists($func)) {
      $isvalid = $func('process', $order, $form_state['values']['panes'][$pane_id]);
      if ($isvalid === FALSE) {
        $_SESSION['expanded_panes'][] = $pane_id;
        $_SESSION['checkout_valid'] = FALSE;
      }
    }
  }

  $order->line_items = uc_order_load_line_items($order, TRUE);

  uc_order_save($order);
}

Note that the iteration through the $form_state['values']['panes'] array just takes the panes in whatever order the array has been built in... I was seeing them in the same order that they were presented on the checkout page, but not sure if D6 core FAPI is populating that array in the same order it was created by the original FAPI form construction, or if it was a coincidence. Might also explain why that error occurs so inconsistently and has proven to be so hard to pin down.