View menu routes missing until first page load
Problem background

I actually found an answer to this problem. Drupal has a rather aggressive way of deleting menu items that has the router_path field set to NULL (or empty) in table menu_links. If Drupal finds such a record it will delete the record upon the next run of menu_rebuild(); (see docs) or documentation block below.

/**
 * Populates the database tables used by various menu functions.
 *
 * This function will clear and populate the {menu_router} table, add entries
 * to {menu_links} for new router items, and then remove stale items from
 * {menu_links}. If called from update.php or install.php, it will also
 * schedule a call to itself on the first real page load from
 * menu_execute_active_handler(), because the maintenance page environment
 * is different and leaves stale data in the menu tables.
 *
 * @return
 *   TRUE if the menu was rebuilt, FALSE if another thread was rebuilding
 *   in parallel and the current thread just waited for completion.
 */


Solution

Each menu item created this way must contain the property customized and have its value set to to 1. This forces Drupal to update the record in table menu_links with the matching router_path instead of deleting it. See function _menu_navigation_links_rebuild($menu) around line 2929 in menu.inc. _menu_navigation_links_rebuild($menu) is called from menu_rebuild().

Example

This will create a new link on the top level in a menu named 'your-menu-name'.

$ls = array(
  'menu_name' =&gt; 'your-menu-name',
  'link_title' =&gt; 'Your Link Title,
  'link_path' =&gt; 'your/link/path',
  'plid' =&gt; 0, 
  'weight' =&gt; 0, 
  'customized' =&gt; 1, // "The magic property"
);

$newpid = menu_link_save($ls);