I know this is an older post but I was looking to do something very similar and it took me a while to figure it out - so I'm sharing in case someone else finds it useful.
I did use the hook_civicrm_navigationMenu. But most of the documentation surrounded how to add something, not remove it. I used the unset function (just like it is used in the hook_civicrm_tabset). The only tricky part is adding the right references to hide the correct menu. For me, I wanted to hide the Mailings menu for 'uncertain' users as @davejenx describes them.
// identify id of Mailings menu in $params array
$mailingsmenuID = CRM_Core_DAO::getFieldValue('CRM_Core_DAO_Navigation', 'Mailings', 'id', 'label');
// remove the menu