When is cache_menu flushed? I was caching some goodies related to the menu, and putting it in the 'cache_menu' bin, assuming they would get cleared whenever someones edits the menu.

cache_set($cachekey, $mymenu, 'cache_menu', CACHE_TEMPORARY);


When I edit the menu, it isn't cleared. When is it cleared, then? 

In what sense is it different from the cache bin?
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.