I too had the same issue as the OP.
I worked through the documentation but also got the same output.
ld = ldap_sslinit("l****.*********.ca", 636, 1);
Error 0 = ldap_set_option(hLdap, LDAP_OPT_PROTOCOL_VERSION, 3);
Error 81 = ldap_connect(hLdap, NULL);
Server error: <empty>
Error <0x51>: Fail to connect to l****.*********.ca
I ensured that any NSG within our subscription (3 in total) had the rule to permit the connection on TCP 636 from a public IP address that I was using for testing.
The client cert had been added to the machine running LDP.exe.
The certificate wss installed, and Secure LDAP set up on the subscription/domain.
I too was running with no on-premise infrastructure, everything is Azure based.
This was a major roadblock to our adoption of Azure.
Then I checked the Event Viewer and found that the certificate was not trusted, but the documentation clearly shows the following:
I installed the certificate into Trusted Root and tested connection again.
BOOM! It works.
Note to self.... don't rely exclusively on Microsoft documentation!