Additionally, today I found myself in a situation where reversing the order of *just* the objectClasses in the filter - i.e., from (&(|(objectClass=foo)(objectClass=bar))(uid=jdoe1)) to (&(|(objectClass=bar)(objectClass=foo))(uid=jdoe1)) - didn't fix things, but changing the search base (from ou=Users,dc=example,dc=com to dc=example,dc=com) did.

I was then able to issue the original search with searchbase ou=Users,dc=example,dc=com and filter (&(|(objectClass=foo)(objectClass=bar))(uid=jdoe1)) and it worked fine. Strange...