If the organisation uses Windows Authentication then it could be that they do not have access to the AddressLines stored procedure. In order for IDLookup to work properly they need to be have the rights to execute this stored procedure.

In theory this could also be the case if they have set up their own SQL Server authenticated user. If that user does not have the rights to execute the AddressLines stored procedure then IDLookup will not find addresses with a specific address line even though other searches may work fine.