Sometimes shipping and/or billing address is missing
I've had similar problems before, never did get to the bottom of it. I think it's related to the Commerce Addressbook module and the way it copies profiles but time ran out before I could confirm.

As a rather hacky (but effective) workaround I used the following to make sure the profile had been copied:

function MYMODULE_form_commerce_checkout_form_checkout_alter(&amp;$form, &amp;$form_state, $form_id) {
  $form['buttons']['continue']['#submit'][] = 'MYMODULE_commerce_checkout_form_submit';
}

function MYMODULE_commerce_checkout_form_submit($form, &amp;$form_state) {
  // If the copy address checkbox is selected.
  if ($form_state['values']['customer_profile_shipping']['commerce_customer_profile_copy']) {
    $order_wrapper = entity_metadata_wrapper('commerce_order', $form_state['order']);
    $shipping_address = $order_wrapper-&gt;commerce_customer_shipping-&gt;commerce_customer_address-&gt;raw();
    $billing_address = $order_wrapper-&gt;commerce_customer_billing-&gt;commerce_customer_address-&gt;raw();

    // If the shipping and billing address aren't the same then we need to fix it.
    if ($shipping_address != $billing_address) {
      $order_wrapper-&gt;commerce_customer_shipping-&gt;commerce_customer_address = $billing_address;
      $order_wrapper-&gt;commerce_customer_shipping-&gt;save();
    }
  }
}


It may or may not work as-is, but even if not it might provide a starting point for debugging.