When is cache_menu flushed?
Looking at menu_link_save(), you will see that it calls menu_cache_clear() to clear only the cache of the menu the menu item belongs to. Other entries in the menu cache are not cleared.

The entire menu cache is only cleared when menu_cache_clear_all() is called directly (eg. by menu_enable(), which runs whenever a module is enabled) or indirectly (often through menu_rebuild() or drupal_flush_all_caches()).

If I were you, I would store my own data in the default 'cache' bin. I consider the menu cache to be private to the menu system; I don't want to touch it and accidentally mess something up. To clear my cache data at the right moment, I would implement hook_meu_link_insert() and/or hook_meu_link_update() and clear/rebuild my cache data from there.