How to instruct Postfix to wait until the LDAP server is back again?
What about just increasing the timeout for LDAP lookups? The ldap_table man page has details. The default is 10 seconds. If it's not a timeout issue -- that is, if the LDAP server is actually rejecting connections -- maybe you could set up a local replica on the Postfix server. Whether or not this is possible depends a lot on your environment and which server you're running.
You could also look at NSCD in order to cache the results from LDAP.