I'm having an odd problem with a simple search filter and the order (with at least) uid and objectclass criteria.
"(&(uid=anyuser)(objectclass=posixaccount))" doesn't work. "(&(objectclass=posixaccount)(uid=anyuser))" works.
How does your index configuration look like? You should have an equality index for yttribute 'uid'.