Is there any reason that you have to traverse the scene in a particular order to begin with?

In my experience, the main use of this kind of tree is hierarchical transforms -- i.e. attachments and skeletons.

To implement those, you just need to ensure that the node-container is sorted such that parents always come before their children, and then do a linear iteration through the container to generate the world-transforms from the parent's world-transform and the current node's local transform. To make this fast, the process that performs this task should be able to access only the parent IDs, the (output) world matrices, and the local matrices.

After that task is complete, the scene can be traversed in any order at all for rendering purposes.

The last game that I worked on actually had multiple of these node-containers per scene (usually one per character), so that they could be parallelized even more effectively. After a character's scene nodes had been computed, it was possible for rendering commands for that character to be submitted, even if other parts of the scene were still being updated.

My ID-based pool has a layer of indirection and each element stores index to the indirection-vector so I can swap them in memory (exactly to avoid fragmentation and do swap-with-last to remove).

If you delay the swapping etc. to the end of the frame or such, you might be able to use the element vector indices directly for temporary things (to avoid going through indirection layer).

That be wasteful if only a few nodes needed to be updated. But then again if its once per frame maybe its not an issue...?

You can always use some kind of bit-field to keep track of which regions of the array are dirty, and then skip over coarse regions. It's then still a linear search, and can still be paralleled easily by splitting up the "coarse regions" between threads.
e.g. instead of having a dirty flag on every single node in the array, maybe you have a bit array where each bit indicates that 16 nodes are dirty. That lets you track the (coarse) dirty status of 2048 nodes with a single SSE __m128i register.

Also, the most important situation to optimize for in a game is the worse-case performance.
Say you're making a game where 100 animated characters charge at you at a time, and each of them has 100 bones -- that means your node hierarchy system has to track 10k nodes.
It's no point doing all sorts of fancy lazy-update / dirty-tracking optimizations if they don't actually help you in this worst case scenario.
Having all those enemies frustum culled (and then not updated) when they're off-screen is nice, and something you should probably do... but it's an absolutely useless optimization if your framerate is below-target when they are all on screen and un-cullable
A solid 30Hz framerate is much better that one that continually alternates between 60Hz and 15Hz, so just keep overall performance in mind when implementing techniques that only benefit certain use-cases. It also helps to have statistical data on what your typical usage situation is. e.g. One game might have 200 characters loaded but on average only 2 are visible, but another game might have 20 characters loaded and on average have 19 visible. The "correct" optimization strategies will be different for those two games.

My ID-based pool has a layer of indirection and each element stores index to the indirection-vector so I can swap them in memory (exactly to avoid fragmentation and do swap-with-last to remove).

Yeah I've seen this used quite a bit. It allows external systems to use simple integer IDs, while allowing the internal system to reorder items whenever it needs to. Often you want to compact your "active"/"dirty" items, so that your update loop has a nice solid, contiguous block of the array to process.