1) Has the vendor gotten this to work correctly with other partners before?
2) Can you use ADSIEdit (from 2003 support tools) to connect to the secured LDAP directly from the server on port 636? How about from a client box on your LAN?
3) Are they using passwords to log into the secured LDAP or smartcard authentication?
4) Is there a software firewall, etc. (e.g. Windows Firewall) on the DC that may be blocking 636?
5) Check to see if your firewall supports passing secured UDP traffic, or if it is restricted to TCP only. Both UDP and/or TCP may be in use here - maybe only some of the traffic is being passed?
Side suggestion to research:
Allowing any 3rd party direct access to your Active Directory is generally not a good idea. There may be specific cases where it is necessary, however 9/10 time this can be avoided by using Active Driectory Application Mode (ADAM) which is an isolated LDAP server. That way you can give the partner whatever access necessary to that LDAP but they will not have any ability to browse or in some worse cases modify your AD. This is a bit more complex of a topic, but may just be worth looking into... If the time and learning how to work directly with LDAP goes beyond what you can afford, maybe looking for a consultant that deals with this specifically might be wise.