It takes forever to start a build in Jenkins and to find an idle slave for it

We are operating one Jenkins master and about 70 swarm slaves with various operating systems. All machines are virtual running on a VMware ESX server.

For some months we are faced with these issues:

• When you manually trigger a build using the web interface it takes about ten minutes for the build to be scheduled as waiting in the list.
• When the job finally is in the build queue, it takes another ten minutes for master to recognize there is an idle build node which can actually perform the build.
• Sometimes a node is shown busy in the node list, but when you look at it the job there is already done.

I cannot present what I've done before, since I have no clue where to start with this. I'm thankful for any clue where to look at or what to try.

What in the end made the difference for us was enabling LDAP caching like described here.

(Global Security => Advanced Configuration)