Hi Drew,
In my testing what happens is exactly what is expected to happen. If you remove a parent from the menu its children are also removed but it does not mess up the menu. Its only logical that in a hierarchy if you hide a node its child nodes will also be hidden, they cannot jump up to the parent level.
Different arrangements can be made to work when using multiple menus because by starting node offsets you can make a child page appear in a sub menu that starts beneath the level with the hidden page so the solution Joe Davis uses is like that with horizontal menu(s) and then a final vertical sub menu that can go as deep as needed.. A page knows its parent id but that is all it knows it does not know the properties of its parent such as if its hidden. So by binding it in a menu that starts immediately below its parent a child page can be shown even though its parent is not in the menu above it.
If you look at demo.mojoportal.com right now it is using the jsavard-mojoportal skin which has a vertical menu for the main menu.
I created a root level page named parent and added some children to it then I made it not appear in the menu. So now neither it nor its children are visible in the menu but are visible in the site map.
Hope it helps,
Joe