If items on the Select Site Map Menu Links tab are unchecked and saved, they are checked again if you return to the General Tab and Save the General Settings. If there were a lot of links being hidden from the links tab, it was difficult to remember which ones you had unchecked.

I was able to fix it by changing the name of the form value that was being checked for in the removal section of menu_site_map_settings_form_submit in the menu_site_map.admin.inc file.

In the 6.x-1.0-beta4 version on about line 169:

  // Delete any menu link data that we have for menus that are no longer
  // part of the site map.
  if ($op == t('Reset to defaults')) {
      db_query("DELETE FROM {menu_site_map_links}");
  }
  else {
    $query = "SELECT DISTINCT menu_name FROM {menu_site_map_links}";
    $result = db_query($query);
    $menu_names = array();
    while ($row = db_fetch_array($result)) {
      $menu_name = $row['menu_name'];
      if (!isset($form_state['values']['menu_site_map_menu'][$menu_name])) {
        db_query("DELETE FROM {menu_site_map_links} WHERE menu_name = '%s'",
                 $menu_name);
      }
    }
  }

I changed line 180 to match this:

if (!isset($form_state['values']['menu_site_map_menus'][$menu_name])) {

The isset function was looking for a form item that didn't exist so it was always removing all entries from the menu_site_map_links table.

If I knew how to roll and submit patches I would, but I hope this can be helpful in some way.