Are consumers of this structure more likely to hold pointers to the parent or to a child?
It sounds to me as though you want more direct control over the lifespans of parent and child. What if the parent's destructor were to delete all children outright? Then you'd never have orphans.
You could hand out shared_ptrs to the parent object, so that it would persist as long as it had any consumers. As soon as the last consumer forgot about it, it would clean up all its own children.
With that arrangement, you'd probably want direct consumers of the children to get weak_ptrs rather than shared_ptrs. That way a consumer could tell if the child had vanished.
The parent should then hold the only shared_ptr to each child. (I'd suggest that the parent track its children with dumb child* pointers, but you need a shared_ptr on which to base your weak_ptrs.)
And -- since you now know that the existence of a child implies the existence of its parent -- you could use dumb parent* pointers for the back-references from child to parent. That eliminates the need for the parent to obtain shared_from_this at constructor time.
Does this address your constraints?
This could help. However handing out a weak_ptr does not prevent situations that it is converted to a shared_ptr, while its parent is destroyed in the same calling sequence (later on). It sounds a little bit theoretical, but I had the hope (some day) that shared_ptr would be a replacement for raw pointers in almost every situation (preferably without thinking). I played a while ago with c# and its gc and I must admit that it works a little bit smoother than shared_ptr/weak_ptr's (dealing out raw pointers to all subsystems is like stoneage programming). Using gc has its own set of dynamics (non deterministic destruction, no use of references in finalizers), so you still have to think from time to time, but I got the impression that it would relieve a programmers job (for lets say 20-30%).