wp_delete_auto_drafts() deletes links in menus

This is what normal query run by wp_get_associated_nav_menu_items() looks like:

SELECT wp_posts.* 
FROM   wp_posts 
       INNER JOIN wp_postmeta 
               ON ( wp_posts.id = wp_postmeta.post_id ) 
WHERE  1 = 1 
       AND wp_posts.post_type="nav_menu_item" 
       AND (( wp_posts.post_status <> 'trash' 
              AND wp_posts.post_status <> 'auto-draft' )) 
       AND (( wp_postmeta.meta_key = '_menu_item_object_id' 
              AND Cast(wp_postmeta.meta_value AS CHAR) = '3111' )) 
GROUP  BY wp_posts.id 
ORDER  BY wp_posts.post_date DESC 

This is what yours looks like:

SELECT wp_posts.* 
FROM   wp_posts 
       INNER JOIN wp_postmeta 
               ON ( wp_posts.id = wp_postmeta.post_id ) 
       LEFT JOIN wp_postmeta AS mt1 
              ON ( wp_posts.id = mt1.post_id 
                   AND mt1.meta_key = '_stealth-publish' ) 
       INNER JOIN wp_postmeta AS mt2 
               ON ( wp_posts.id = mt2.post_id ) 
WHERE  1 = 1 
       AND wp_posts.post_type="nav_menu_item" 
       AND (( wp_posts.post_status <> 'trash' 
              AND wp_posts.post_status <> 'auto-draft' )) 
       AND ( ( wp_postmeta.meta_key = '_menu_item_object_id' 
               AND Cast(wp_postmeta.meta_value AS CHAR) = '3244' ) 
              OR mt1.post_id IS NULL 
              OR ( mt2.meta_key = '_stealth-publish' 
                   AND Cast(mt2.meta_value AS CHAR) != '1' ) ) 
GROUP  BY wp_posts.id 
ORDER  BY wp_posts.post_date DESC 

It would be my guess that _stealth-publish stuff has no business whatsoever interfering with querying for nav menu items.