Why doesn't my code to save an order work when invoked by AJAX?
The reason you are getting page not found is might be because of security check. In other words why any user can not access checkout page for any other user.For authenticated user drupal manages the mapping of order id and user id, but when user is anonymous drupal checks if the accessed order id is in current session or not, so while creating the order progammatically we do not need to explicitly set the order into session.
A nice example:
commerce_cart_order_new()

Creates a new shopping cart order for the specified user.

When you are on the commerce_cart_order_new() api page, check the codes after comment

// If the user is not logged in, ensure the order ID is stored in the
session.

That is how drupal cart does while creating order for anonymous user.
Reason:
Before a user a able to move to checkout page drupal checks if the current user has access or not using commerce_checkout_acess().For authenticated user it simply checks if the current user id is same as the order owner user uid if so user can move to checkout page.For anonymous user drupal checks SESSION, if in current session acsessed order id exists user can move to checkout page or access is granted to user.
Solution:
Use of commerce_cart_order_session_save() to set the session like drupal cart does.So your code will look like
$product_id = 1;
global $user;
$order = commerce_order_new($user-&gt;uid, 'checkout_checkout');
commerce_order_save($order);
$product = commerce_product_load($product_id);
$line_item = commerce_product_line_item_new($product, 1, $order-&gt;order_id);
commerce_line_item_save($line_item);
$order_wrapper = entity_metadata_wrapper('commerce_order', $order);
$order_wrapper-&gt;commerce_line_items[] = $line_item;
  // If the user is not logged in, ensure the order ID is stored in the session.
  if (!$user-&gt;uid) {
    commerce_cart_order_session_save($order-&gt;order_id);
  }
commerce_order_save($order);
drupal_goto('checkout/' . $order-&gt;order_id);