I am using 2.4.16. The problem is, that caching seems to work for some entries but not for others. It is not related to the order of the filter rules. Here is what happens: (lines starting with *** are my comments)

**** slapd is started showing version, query templates and attributes

bash-2.05# ./slapd -d 4096 @(#) $OpenLDAP: slapd 2.4.16 (Jun 30 2009 16:56:26) $

jim@flits:/net/build.sparc/management/openldap/openldap-2.4.16/servers/slapd /opt/openldap/openldap-2.4.16/etc/openldap/slapd.conf: line 78: rootdn is always granted unlimited privileges. /opt/openldap/openldap-2.4.16/etc/openldap/slapd.conf: line 85: rootdn is always granted unlimited privileges.

This tells us you have some ACLs in place. Could you show them? Actually, could you post your whole slapd.conf, if you're using any, or the contents of your cn=config database? Of course, after removing any sensitive information, like passwords.

p.