How can I clear menu cache when updating module settings?

I have created a small module (which I'll call "mymodule" here, names changed to protect the innocent) which shows a custom page. In this simplified example of what I'm attempting to accomplish, once the module is installed and enabled, a new "My Module Page" link shows up on the Navigation menu, and when it's clicked, a page is displayed with some dynamically-generated content, with "My Module Page" as the page header. But in the settings of my module, I allow the site admin to change the title of this page. How? Here is the hook_menu code for my module:

function mymodule_menu($may_cache) {
	$items = array();
	if ($may_cache) {
		$items[] = array(
			'path' => 'mymodule',
			'title' => variable_get('mymodule_title_of_page', t('My Module Page')),
			'access' => user_access('access content'),
			'callback' => 'show_mymodule_page'
		);
		$items[] = array(
			'path' => 'admin/settings/mymodule',
			'title' => t('My Module Settings'),
			'description' => t('Settings for My Module.'),
			'callback' => 'drupal_get_form',
			'callback arguments' => array('mymodule_admin_settings'),
			'access' => user_access('administer site configuration'),
			'type' => MENU_NORMAL_ITEM
		);
	}
	return $items;
}

As you can see from the line 'title' => variable_get('mymodule_title_of_page', t('My Module Page')), the menu entry for the item is dynamically named based on what the user entered on the Settings page (which, obviously, has a text field for "mymodule_title_of_page"). The problem is that when the user changes the value for this setting, it is not reflected in the menu or the title of the page because the cache_menu table still has the old name in it. I know the following code is supposed to clear the cache:

cache_clear_all(NULL, 'cache_menu');

But I have two problems I can't seem to solve:

1. The function doesn't work, and the cache is NOT cleared unless I do it manually
2. Assuming I get the function to work, how do I invoke it every time the settings are changed?

I guess I can invoke the cache-clearing when displaying the settings form, by adding it to the mymodule_form() function. That might solve the problem anyway, since it re-displays after submitting. But as a purist, I want it to invoke upon submission, via some kind of hook that simply invokes the code whenever the settings change. I can't find any such hook. Is there a way?

P.S.: I have also considered using drupal_set_title to simply set the title of the page to the new variable upon displaying the module page. But I can still see instances where using a Settings page to change a menu item's title and page title could be useful. So any insight would be appreciated!!!