This long night (one hour more when changing from summer to winter time here in Europ), I open a new ticket #15264 for an unpleasant bug in taxonomies and relationship with new navigation menu features.
Discovered with taxonomies ‘dictionary’ used by xili-dictionary since WP 2.3, this unexpected delete of nav menu item also occurs if a term is shared between a category and a post_tag.
The next release (1.2.2) of xili-dictionary will fixe this defect with a workaround. But, in default conditions, be aware that delete a tag can delete the nav menu item based on a category with the same term !
Don’t hesitate to open a topic in dev.xiligroup forum !