In case it could benefit to anyone, the freeze seems to come when there're "lots of" "deferring operation: binding" messages in the slapd logfile. So, we investigated the corresponding client application and found the way it dealt with LDAP connections could be a problem with OpenLDAP (it was not with Sun DS 5.2 !). So, we're now in the process of rewriting the client side LDAP connections management with a pool, so that at least we don't see anymore "deferring operation: binding" messages.
By the way, are there well known best practices and pointers to write clean (from a connection management point of view) LDAP clients, or at least best practices or "known bad practices" with regards to the way OpenLDAP deals with connections ?