I would like to use openldap/pam_ldap to authenticate 10000 or so users,
but when building the solution in the lab I am getting horrible
performance. It is taking 4-5 secs to find a user in the directory and
authenticate.
You already answered your question - you don't have indexes on the
attributes you use for searches.