Query External LDAP Server from SQL Server
What stands out the most in your second error message is the message below:


  The provider indicates that the user did not have the permission to perform the operation


This tells me that the user in your linked server configuraiton doesn't have access to the AD / LDAP server to perform that query. Here is my ADSI configurations along with an example query. You may need to engage your SA team to ensure the account configured in your linked server has the correct access to query AD / LDAP.

    USE [master]
GO

/****** Object:  LinkedServer [ADSI]    Script Date: 11/10/2017 3:46:31 PM ******/
EXEC master.dbo.sp_addlinkedserver @server = N'ADSI', @srvproduct=N'Active Directory Services 2.5', @provider=N'ADSDSOObject', @datasrc=N'adsdatasource'
 /* For security reasons the linked server remote logins password is changed with ######## */
EXEC master.dbo.sp_addlinkedsrvlogin @rmtsrvname=N'ADSI',@useself=N'False',@locallogin=NULL,@rmtuser=N'domain\accountname',@rmtpassword='########'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'collation compatible', @optvalue=N'false'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'data access', @optvalue=N'true'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'dist', @optvalue=N'false'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'pub', @optvalue=N'false'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'rpc', @optvalue=N'false'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'rpc out', @optvalue=N'false'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'sub', @optvalue=N'false'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'connect timeout', @optvalue=N'0'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'collation name', @optvalue=NULL
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'lazy schema validation', @optvalue=N'false'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'query timeout', @optvalue=N'0'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'use remote collation', @optvalue=N'true'
GO
EXEC master.dbo.sp_serveroption @server=N'ADSI', @optname=N'remote proc transaction promotion', @optvalue=N'true'
GO


Here is an example of using the the ADSI linked server using openquery, but you need to understand the OU structure and the domain structure of AD before building the LDAP connection string. 

SELECT sn, displayName, givenName, mail, telephoneNumber, ipPhone, sAMAccountName
FROM OPENQUERY(ADSI, 
'SELECT sAMAccountName, displayName, telephoneNumber, ipPhone, mail, givenName, sn 
FROM ''LDAP://DC=test,DC=intranet,DC=com'' WHERE objectCategory = ''Person'' AND objectClass = ''user''')
AS derivedtbl_1


NOTE: I changed the DC name in the LDAP string for security reasons, but you should be able to get the idea.