Duplicate mlids should not be possible

This *is* actually a bug. I think you're misunderstanding what I'm saying. Of course a node can be referenced by multiple menu items. BUT, multiple menu items with the same mlid can *never* exist. If you have multiple rows in menu_node with the same *mlid* (not nid), then there is a problem. This is the duplicate problem I was referring to.

Try this. This is the "edit in place" I was referring to. Create a custom menu, and add a link to a node on the site. Now go back and edit the same menu item. Only change the link to be a different node. What *should* happen is that the menu_node row should either be deleted before a new one is inserted or (as my patch does) updates the row in place to reference the new node id. Instead, what happens, is that the existing row is left behind, basically an orphan, and a new row is inserted to join the node and menu_links together. The fact that the old row is left behind is not a problem of removing duplicate rows in Views (which I'm very aware of how to do), it's a problem of stale and incorrect data.

This gets back to my fundamental point that there really should never be an instance where there are duplicate mlid's in the menu_node table. It should never happen. *That's* how the Drupal Menu system is designed.

Hah, I've often looked back at old code and wondered what I was thinking at the time...

In any case, you're probably right. Knowing the condition things can be in, it would probably be best to code something into the update hook before the indexes are recreated. In our environment, I caught it early enough that I was just going to remove the deadwood manually before running this update hook in production. In the wild, though, it's a whole different ball game. Though, I could see it working something like this:

/**
 * Update to the new schema with only mlid as primary key.
 */
function menu_node_update_6001() {
  $ret = array();
  // First remove any deadwood that may have accumulated
  $result = db_query('SELECT mlid, count(mlid) AS rowcount FROM {menu_node} GROUP BY mlid HAVING rowcount > 1');
  while($mlid = db_fetch_object($result)) {
    $link_path = db_result(db_query("SELECT link_path FROM {menu_links} WHERE mlid = %d AND link_path LIKE 'node/%' AND router_path = 'node/%%'", $mlid->mlid));
    if (empty($link_path)) {
      /*
       * Either menu_link row no longer eists or doesn't point to a node.
       * Delete all rows with that mlid
       */
       $ret[] = update_sql('DELETE FROM {menu_node} WHERE mlid = '.$mlid->mlid);
    } else {
      // Delete any rows not referencing the returned nid
      $nid = str_replace('node/', '', $link_path);
      if (is_numeric($nid)) {
        $ret[] = update_sql('DELETE FROM {menu_node} WHERE mlid = '.$mlid->mlid.' AND nid <> '.$nid);
      }
    }
  }
  // Now drop the old primary key and create the new primary key and index
  db_drop_primary_key($ret, 'menu_node');
  db_add_primary_key($ret, 'menu_node', array('mlid'));
  db_add_index($ret, 'menu_node', 'nid', array('nid'));
  return $ret;
}