This is some extremely ugly code. My first instinct is to rewrite it to eliminate the recursion but I have a feeling that may be too drastic a change.

Another thought is to alter wait4msg/try_read1msg's parameter list to specify which lconn to start from, and order the list such that the recursive calls can only iterate over the newest lconn structures. That would prevent them from freeing lconns that are currently being referenced by a prior caller. (That would also prevent them from parsing any received data that's ready on other connections, until the Bind on the new referral connection completes. So this may needlessly serialize some work and decrease overall throughput when references are interleaved in a larger result set.)

And yet another approach is simply to bump up each lconn's refcnt, the same way request.c:ldap_new_connection() does, to prevent them from getting freed prematurely. This latter approach would be simplest, except it requires calling ldap_free_connection() to actually decrement the refcnt, and that requires more mutex manipulation for the libldap_r version. (I haven't looked too deeply into the lock dependencies yet, it may actually be simpler.)