6 minutes for 25000 entries is obviously too much. On our server  (HP of two years old ang 2Go of memory)  8300 entries are returned in 0.77 seconds (the filter is almost like yours - "(&(uid=*)(objectClass=inetOrgPerson))"). There is certainly some problem either with the disk access or with the memory sizing or with the indexed searches in your configuration... Do you have the PRESENCE index on uid?

2009/10/27 Juan Asensio Sánchez <okelet@gmail.com>
> How many entries match this search filter?  Is your nsslapd-idlistscanlimit
> high enough to hold both all of the uid=* entries and all of the
> objectClass=sambasamaccount entries?

We have about 25000 sambaSamAccount objects. nsslapd-idlistscanlimit
is set to 50000 (total object are about 40000). Databases have been
reindexed.