Тест-стадия затянулась, прошу прощения.
Всё замечательно работает и на вебсервере. Могу порекомендовать в качестве стандартного решения.
(Интересно, а в 5ой версии эта "проблема" осталась?..)

Спасибо огромное, Natalie!
Одна из этих идей работает именно так, как нужно. А именно, хак ninetwenty от 26го августа в модуле menu.inc.
Протестировал с версией Drupal 4.7.4 и с модулем node privacy byrole, версии 4.7.0. Использовал 4 пункта в меню, 5 пользователей и 3 роли. Заработало после чистки кэша. Тестировалось локально под виндами на xampp'e. Посмотрю на следующей неделе, как это будет на сервере.