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' => 'navigation',
'weight' => 0,
'link_title' => '',
'hidden' => 0,
'has_children' => 0,
'expanded' => 0,
'options' => array(),
'module' => 'menu',
'customized' => 0,
'updated' => 0,
);