As far as I understand from the code, libldap already behaves like that, i.e. it
loops through all the hosts returned by getaddrinfo(3). What's missing (in your
configuration of ldapsearch) is a network timeout parameter. Right now, you can
set it either using NETWORK_TIMEOUT in ldap.conf(5) or passing the command-line
switch -o nettimeout=<timeout>. I understand the latter is not documented in
ldapsearch(1), although it appears in the usage message of all tools.
As I'd consider this issue a software usage question rather than a bug (except
for the missing documentation), I encourage you to continue discussion on the
openldap-technical mailing list.