I have a server with 20,000 account entries and one group that has 10,000 members. Deleting members from that group is very slow on OpenLDAP 2.4.10, though adding goes at a reasonable speed.
Try configuring sortvals - see slapd.conf(5).
-- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/