Yes, they do (of course).
But for some reason, I just hadn't thought of it before (either way), and it made me wonder for a bit yesterday. Conclusion: yes, the virtual dom tree is memoized, but only up to contained component instance references, which will then handle their (re)rendering on their own terms. Another way to think of it: memoization of some virtual dom tree structure doesn't mean that it's excluded from the diffing algorithm, it only means that it's not recomputed (entirely).
Here's a small doodle to explore: