hook_menu_get_item_alter() needs to give a 404
I was able to do this in hook_menu_get_item() by getting the status of the node from a simple query, and, when status isn't NODE_PUBLISHED, I change the router item's load function from node_load() to is_null(), which will always return FALSE when a node ID is passed to it. A FALSE from a load function will result in a 404 response from Drupal. This is a bit dirty, but it uses the Drupal API properly, and it seems to work!

/**
 * Implements hook_menu_get_item_alter().
 */
function mymodule_menu_get_item_alter(&amp;$router_item, $path, $map) {
  if ($path == $_GET['q']) {
    if (isset($map[0]) &amp;&amp; $map[0] == 'node' &amp;&amp; isset($map[1]) &amp;&amp; is_numeric($map[1])) {
      $status = db_query('SELECT n.status FROM {node} n WHERE n.nid = :nid', array(':nid' =&gt; $map[1]))-&gt;fetchField();
      if ($status != NODE_PUBLISHED) {
        // Replace node_load() with is_null() as load function, to ensure the
        // output of the load function is FALSE, so we get a 404 response.
        $router_item['load_functions'] = array('is_null');      
      }
    }
  }
}