menu items saved with menu_link_save() don't have the delete button, and I can't edit the menu path
The reason the "delete" link is not shown is that the link is only shown when the menu item is created by (or associated to) the Menu module. _menu_overview_tree_form() contains the following code:

  // Only items created by the menu module can be deleted.
  if ($item['module'] == 'menu' || $item['updated'] == 1) {
    $operations['delete'] = l(t('delete'), 'admin/build/menu/item/' . $item['mlid'] . '/delete');
  }


menu_link_save() uses some defaults for the array $item passed as argument; this means that if the module associated with the menu link is not explicitly set, it receives the default value ("menu").

  // Load defaults.
  $item += array(
    'menu_name' =&gt; 'navigation', 
    'weight' =&gt; 0, 
    'link_title' =&gt; '', 
    'hidden' =&gt; 0, 
    'has_children' =&gt; 0, 
    'expanded' =&gt; 0, 
    'options' =&gt; array(), 
    'module' =&gt; 'menu', 
    'customized' =&gt; 0, 
    'updated' =&gt; 0,
  );