It turns out this solves my reindexing issue. Only 2 entries needed to be removed from alf_child_assoc. A further upgrade to 4.2.d showed 2 orphan nodes moved to lost_found (likely the same nodes I removed from alf_child_assoc). And alfresco started in 4.0.e and also in 4.2.d.
I do have backups (working on a copy), so I can easily roll back if something I try fails.