For a recent site, we needed to have a menu block be visible on pages which were represented in the menu. That is to say, if the page you are looking at is in the "Editorial stuff" menu, display the editorial stuff menu block.
The trick here is to use PHP for determining the block visibility for the menu blocks. If we're looking at a node derivative, the node id should be in the link_path field of menu_links. If we're looking at a page created by another module (views for example) then the url will be there.
We run a quick query to check for the existence of the value and return true or false based on the success.
You should be wary of using this if you have more than two or three blocks, since this means a mandatory string lookup query per block and per page. If you've got more than a handful of menus, it'll likely be worth implementing a module with some smarter logic to cut down on the db load.