FULL PRODUCT VERSION :
Several JRE versions have been tested and listed in the "Additional Configuration Information" section.

ADDITIONAL OS VERSION INFORMATION :
Tested on both Ubuntu 12.04 and Redhat 6.3 64-bit
Linux XXX.com 2.6.32-279.1.1.el6.x86_64 #1 SMP Wed Jun 20 11:41:22 EDT 2012 x86_64 x86_64 x86_64 GNU/Linux
Linux jriffle-VirtualBox 3.2.0-29-generic #46-Ubuntu SMP Fri Jul 27 17:03:23 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux

EXTRA RELEVANT SYSTEM CONFIGURATION :
Very SLOW on the following JREs:
1.6.0_33-b04
1.6.0_32-b05
1.7.0_05
1.7.0_03-b04

Works normally on the following JREs:
1.6.0_15-b03
1.6.0_25
1.6.0_27-b07
1.6.0_34-b04
1.7.0_06-b24

A DESCRIPTION OF THE PROBLEM :
A java web application that was designed to make several consecutive queries against an LDAP directory started performing very slowly when moved from JRE 1.6.0_15 to a new server with JRE 1.6.0_33. I discovered our function DirContext.search() was running at about a factor of 10 slower regardless of which physical hardware it ran on. Changing the JRE version can resolve the performance issue but it indicates that there may very well be a Java bug introduced in varying versions of the JRE that squelch the performance of JNDI search.

Tested 600 consecutive queries against Active Directory LDAP using JNDI:

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1) Create a text file with 600 lines of bogus user names

2) Compile the provided example code (that performs the tested query)
Replace:
LDAP_SERVER: Your Active Directory server
LDAP_USER: LDAP path to your user
LDAP_PASS: Password
LDAP_OU: The scope being performed within.
Note: The scope that this error was reproduced within contained several OUs with about 30000 combined user entries. Also, the LDAP's public certificate will need to be imported into JRE's keystore.

3) Send the output of the text file of 600 bogus user names into the input of the compiled java class
Ex: cat listofusers.txt | java test

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
JRE's that run at a normal speed show a time similar to
real 0m2.562s
user 0m1.240s
sys 0m0.564s
ACTUAL -
JRE's that run slowly show a time similar to:
real 2m6.350s (!!!)
user 0m2.430s
sys 0m0.153s


ERROR MESSAGES/STACK TRACES THAT OCCUR :
No special errors are indicated.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import javax.naming.Context;
import javax.naming.directory.*;
import java.util.*;
import java.io.*;
import javax.naming.NamingEnumeration;
import javax.naming.NamingException;

public class test3 {
public static void main(String args[]) {
String[] attrIds = {"sAMAccountName"};
String searchFilter;
String inputLine = null;
Integer i = 0;
NamingEnumeration answer = null;
Hashtable<String, String> env = new Hashtable<String, String>();

java.io.BufferedReader stdin;

try {
stdin = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
} catch (Exception e) {
System.out.println("There was an exception!\n");
return;
}

try {
env.put(Context.INITIAL_CONTEXT_FACTORY,"com.sun.jndi.ldap.LdapCtxFactory");
env.put(Context.PROVIDER_URL, "ldaps://LDAP_SERVER:636");
env.put(Context.SECURITY_PRINCIPAL, "LDAP_USER");
env.put(Context.SECURITY_CREDENTIALS, "LDAP_PASSWORD");

DirContext ctx = new InitialDirContext(env);

SearchControls searchCtls = new SearchControls();
searchCtls.setSearchScope(SearchControls.SUBTREE_SCOPE);
searchCtls.setReturningAttributes(attrIds);

while(true) {

i++;
inputLine = stdin.readLine();
if (null == inputLine) return;
searchFilter = "(&(samaccountname="+inputLine+"))";

answer = ctx.search("LDAP_OU",
searchFilter, searchCtls);

if(answer.hasMore()) {
System.out.println("("+i.toString()+") Found a response!");
} else {
System.out.println("("+i.toString()+") Not found!");
}
}
} catch (Exception e) {
System.out.println("Exception error!");
e.printStackTrace();
}
}
}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Use one of the working versions of JRE. It appears to be hit or miss whether or not this error can be reproduced depending on the JRE version.