Some more information: once I changed the search base from ou=Users,dc=example,dc=com to dc=example,dc=com to "fix" the problem for that particular user (after which the original query with the ou=Users,dc=example,dc=com search base began working again), the following entries popped up in the log: ftp://ftp.openldap.org/incoming/ryan-steele-110221.proxycache-log-fixing-broken-entries.log.1

It gets stranger, though. If I start out by using the root entry as the search base (dc=example,dc=com) with a user who is not yet in the cache, not only will it say it is ANSWERABLE (which it clearly isn't) and then return nothing without even trying to reach out to the upstream host, but if I then change the search base to ou=Users,dc=example,dc=com, I get the following error on the CLI (and this is with a successful bind as the directory admin):

ldapsearch -x -D cn=admin,dc=example,dc=com -y /etc/ldap.secret -H ldaps://localhost -LLL -b cn=admin,dc=example,dc=com '(&(|(objectClass=examplecomUtilityUser)(objectClass=examplecomEmployee))(uid=jdoe4))' uid No such object (32) Matched DN: dc=example,dc=com

Debugging logs generated by that query can be found here: ftp://ftp.openldap.org/incoming/ryan-steele-110221.proxycache-log-attempt-to-fix-broken-entries-error.log.1