"Can't contact LDAP server" errors on RHEL

Issue

We are getting a lot of messages on the clients like this one:

Jan 18 16:19:32 hostname lsof: nss_ldap: failed to bind to LDAP server ldap://192.168.1.223: Can't contact LDAP server

We have over ~15 locations using LDAP, all of them have local slapd servers on their local LAN, so its hard to understand why these messages are so prevalent. I have to conclude that we have a configuration problem on the server side. There are so many of these messages that anytime some other issue comes up the immediate tendency is blame LDAP, although I am not sure this is really the problem.

We have tried turning every switch we know of on the client side (using IP addresses instead of hostnames, using nscd or not using nscd) but nothing makes a difference.