Thank you, everyone, for your superhumanly quick response to this!
I was wondering, if we are going to see a back-port of the fix in D6, as mentioned by webchick.
The same problem is also reproducible for the "Site Building" menu - ie., even if the role has no permissions for any of the menu items in the menu, the menu itself is still displayed. I suspect the same thing might happen also for the "Site Configuration" menu.
This *is* a serious problem to me, as one of the main tasks I have when setting up a Drupal site is to 'dumb down' the admin interface for newbie users. Not being able to easily hide these menus means that the interface ends up being overly complicated for low-level admin users - like site editors, who have no business managing users, or playing around with the site configuration.
Currently, the only way to overcome this bug is to split the Administer menu into several menus (one for each role needed), and use the BLOCK permissions for each menu block individually. In my case, for instance, I ended up having to split the menu into "RegisteredUser", "SiteEditor" and "SiteAdmin" menus. This is not a proper solution, it is a time-consuming, inelegant hack. I end up with 3 or 4 separate menus, containing totally related functions that had to be split in order for me to be able to control role access to them - when they really should be under just a single menu.
I do not need several different menus. I need just ONE menu, that properly restricts its items' visibility according to the user's permissions.
I hope this will be fixed for D7.