Quanah Gibson-Mount writes:
Please provide any tuning that you've done. It's fairly impossible to comment on why you are seeing this behavior without it.
And an exact ldapsearch command line provoking the problem, minus any passwords.
I.e., what are the *cache settings you set in slapd.conf/cn=config? What is the contents of your DB_CONFIG file? Are you using an shm key?
You may wish to read over https://wiki.zimbra.com/wiki/OpenLDAP_Performance_Tuning. You can easily map the information there to a non-zimbra installation.