Should be not that difficult, but as so often the devil is in the detail.
The AD admin created a user that is capable of reading the complete AD - as it is described in the documentation.
Then I tried to login. And tried, and tried. Password was reset, different password was used, etc.
I tried a very easy ldapsearch and received the follwoing error:
80090308: LdapErr: DSID-0C09030B, comment: AcceptSecurityContext error, data 531, v893
HEX: 0x531 - not permitted to logon from this workstation
DEC: 1329 - ERROR_INVALID_WORKSTATION (Logon failure: user not allowed to log on to this computer.)
NOTE: Returns only when presented with valid username and password/credential.
The user was created but the AD admin did not allow the user to login to the machine where the AD was running.