You need to upgrade to OpenLDAP 2.3. There were a lot of gratuitous sched_yield() calls in OpenLDAP 2.2 that were removed in 2.3. These sched_yield() calls behave poorly with the scheduler in the Linux 2.6 kernel.
I installed 2.3.29 from etch, and it works like a dream. It always replies instantly. I even ran two endless loops at nice -19, and the system became really slow, but slapd still replied instantly.
Thanks for the help!