LDAP Bind Vs Search

Question 1

You should definitely not perform a bind simply to determine whether an entry exists. There are a couple of very good reasons for this:

A standards-compliant LDAP server should return an "invalid credentials" response for both the case in which you're trying to bind as a user that doesn't exist and the case in which you're trying to bind with the wrong password. Therefore, if you don't know the password for a user (which is a pretty good bet if you don't even know whether the user exists), then you can't use a bind to differentiate between a missing user and the wrong password.
Bind attempts may result in writes to the target entries, which could significantly degrade performance. If you try to bind with the wrong password, then the server may be configured to keep track of failed authentication attempts, and in some cases may even lock out a user. Even if you bind with the correct password, the server may be configured to update the entry (e.g., to record a last login time).

There are a few other options that you could consider. They include:

As Terry suggested, perform a base-level search for each entry (which is what the LDAPConnection.getEntry method does) with a requested attribute set of "1.1" which means no attributes. If the entry doesn't exist, you'll get a "no such object" result (which will cause the LDAP SDK to throw an LDAPException). If the entry does exist, then you'll get back a search result entry with just its DN, followed by a search result done response.
As an alternative to using a base-level search, you could use an LDAP compare operation. This is more efficient than a search if you just want to know if the entry exists because there is only a single response per entry (a compare result) rather than two (a search result entry and a search result done). If the entry exists, then you'll either get a response of "compare true" or "compare false" based on whether the entry matches the compare assertion. If the entry doesn't exist, then you'll get an LDAPException with a "no such object" result.
If the server you're using supports the entryDN operational attribute (as described in RFC 5020), then you could perform a single search that may be used to retrieve multiple entries. For example, you could construct a filter like "(|(entryDN=uid=user.1,dc=example,dc=com)(entryDN=uid=user.2,dc=example,dc=com)(entryDN=uid=user.3,dc=example,dc=com)(entryDN=uid=user.4,dc=example,dc=com)(entryDN=uid=user.5,dc=example,dc=com))". This example would be for a single search request that could be used to determine which of those five entries exists. Rather than a separate request and response for each entry, you'll have a single request with up to five search result entry responses and one search result done response. I definitely wouldn't recommend constructing an OR filter with 5000 elements, but you could still use this to dramatically reduce the number of search requests you need to perform.
If the directory you're using doesn't have substantially more entries than the ones you're trying to check, then you could simply create a set with the DNs you're looking for, perform a subtree "(objectClass=*)" search, and then remove the DN of each entry from the set as it is returned by the server. When the search is complete, the entries left in the set will be those that don't exist in the server. Of course, this would be a really bad idea if you just want to check for a handful of entries in a server that contains a whole lot of entries.

Note that in the last two cases in which you're attempting to determine whether an entry exists based on whether it's returned in a set of search results, you will also be subject to access control restrictions. If the account you've used to bind to the server doesn't have permission to see all of the entries that you're trying to check, then you might mistakenly think that an entry doesn't exist just because the client doesn't have permission to see it. Conversely, the first two approaches might return a result of "insufficient access rights" if you don't have permission to make the check, so that could also prevent you from making the determination. Ultimately, that means that you should use an account that you're sure has permission to see all of the entries for which you need to make the determination.

Question 2

If the DN is known, and then client is checking for existence and not authenticating, retrieve the 1.1 OID (no attributes), not a BIND. BIND is often slower than search. For example:

try {
    // Connect to the server
    LDAPConnection ldapConnection = new LDAPConnection(...);
    try {
        for(String dn:listOfDns) {
            Entry entry = ldapConnection.getEntry(dn,"1.1");
        }
    } catch(LDAPException ex) {
        // handle an exception from the search
    } finally {
        ldapConnection.close();
    }
 } catch(LDAPException ex) {
        // handle an exception from the connection attempt
 }

Question 3

Don't search if you don't have to. If you already know the DN, just bind to it.

However the usual case is that you know something else, i.e. an attribute value such as mail or displayName, so you have to first search to find the entry with that attribute, then bind with that entry's DN.