After digging into this more, this definitely looks like a bug in openldap. I modified openldap to make all mutex's recursive. Then my GSSAPI rebind proc worked properly, and the search searched all referrals and found the result (two referrals later).
Did you file an ITS? Problems reported on the lists may get lost without one.
<http://www.openldap.org/its/> --Quanah -- Quanah Gibson-Mount Principal Software Engineer Zimbra, Inc -------------------- Zimbra :: the leader in open source messaging and collaboration