Root cause: Strange OpenLdap performace issue

["Michele Mase'" <michele.mase@gmail.com>]

I've a tiny ldap service (only 6000 records) vith openldap 2.3.x rhel5.x master/slave;
The first query takes me over 4 seconds (instead of taking less than 0.1.seconds):
time ldapsearch -x -b "c=it" -s sub "(o=*)" -D "cn=Manager,dc=sir" -h www.example.com -w mypasswd
The same query using one level takes only 0.4 seconds
time ldapsearch -x -b "c=it" -s one "(o=*)" -D "cn=Manager,dc=sir" -h www.example.com -w mypasswd

I've tested the following:
New brand system with openldap 2.4.x rhel6.x mirror mode: both queries take me less than 0.2 seconds
New brand system with the same releases, 2.3.x rhel5.x: both queries take me less than 0.2 seconds

The problem should be in the prod. system:
I've tried almost all: reindexing operations, better indexing options, more cache, better threads tuning, more cpu and ram to the servers ... nothing to do: the first quey takes more than 4 seconds.

The last operation was a "disaster recovery" of the prod. ldap:
1 stop ldap on both systems
2 slapcat to save the last good ldif
3 remove of all databases (rm -fr /var/lib/ldap/*) on both systems
4 recreate dirs, DB_CONFIG and restore ldif; restore permissions
5 start ldap service on both servers

And magically, the issue has gone!
Now first query, yes the "bad" query with the subtree options, works like a charm, giving me the results in less than 0.1 seconds ....

Which could be the root cause? DB defragmentation? I was unable to find the root cause. PLS, help me to find some suggestions.

Regards
Michele Masè