In writing some more tests and looking at performance data while adding nodes, I found another potential significant bottleneck not only for adding nodes but also for setting properties: AbstractJcrNode#isCheckedOut (called both from #addNode and #setProperty). This is especially visible when running a deep hierarchy of nodes, where this method will load the entire hierarchy of parents for a child node, no matter how deep.
Is there any way we can optimize this (e.g. store some sort of boolean flag each time we check out a node, so that we can easily compute the checked out status of a path. Or looking at the node types for mix:versionable) ?