Created attachment 8982 [details]
testCase.py

Created attachment 8983 [details]
0001-s4-rpc_server-pick-CN-System-CriticalSystemObject.patch

E.g. search '(&(objectClass=container)(cn=system)(isCriticalSystemObject=True))'

Confirmed.
It almost took me a day to figure this out.
Besides joining also login is affected on W2008/2012 machines.

Please consider the supplied patch for merge.

We just had this again with samba 4.3.7, took a new colleague another day digging though network traces. For the record, these are the parts of log.samba characteristic for this situation:

=============================================================================
[2016/08/10 15:00:50.317533,  1, pid=25834, effective(0, 0), real(0, 0)] ../librpc/ndr/ndr.c:439(ndr_print_function_debug)
       netr_DsrEnumerateDomainTrusts: struct netr_DsrEnumerateDomainTrusts
          in: struct netr_DsrEnumerateDomainTrusts
              server_name              : *
                  server_name              : '\\somedc.domain.local'
              trust_flags              : 0x0000003f (63)
                     1: NETR_TRUST_FLAG_IN_FOREST
                     1: NETR_TRUST_FLAG_OUTBOUND 
                     1: NETR_TRUST_FLAG_TREEROOT 
                     1: NETR_TRUST_FLAG_PRIMARY  
                     1: NETR_TRUST_FLAG_NATIVE   
                     1: NETR_TRUST_FLAG_INBOUND  
                     0: NETR_TRUST_FLAG_MIT_KRB5 
                     0: NETR_TRUST_FLAG_AES
[...]
[2016/08/10 15:00:50.329686, 10, pid=25834, effective(0, 0), real(0, 0), class=ldb] ../lib/ldb-samba/ldb_wrap.c:72(ldb_wrap_debug)
  ldb: ldb_trace_request: SEARCH
   dn: DC=domain,DC=local
   scope: sub
   expr: (&(objectClass=container)(cn=System))
   attr: <ALL>
   control: <NONE>
[...]
[2016/08/10 15:00:50.331385,  1, pid=25834, effective(0, 0), real(0, 0)] ../librpc/ndr/ndr.c:439(ndr_print_function_debug)
       netr_DsrEnumerateDomainTrusts: struct netr_DsrEnumerateDomainTrusts
          out: struct netr_DsrEnumerateDomainTrusts
              trusts                   : *
                  trusts: struct netr_DomainTrustList
                      count                    : 0x00000000 (0)
                      array                    : NULL
              result                   : WERR_GENERAL_FAILURE
=============================================================================

(In reply to Arvid Requate from comment #4)
Hi Arvid,

I'd like to use CN=System,$DEFAULT_DN, instead
of doing a search.

We're using ldb_dn_add_child_fmt(system_dn, "CN=System");
in a few places already. See dsdb_trust_search_tdo[s]().

Can you provide an updated patches?
One for each subdirectory? Also remember
we have two backupkey implementations now.

Created attachment 12413 [details]
Bug-9959-master.patch

Patch set for master

Created attachment 12414 [details]
Bug-9959-v4-4-stable.patch

Patch set for v4.4-stable

Created attachment 12415 [details]
Bug-9959-v4-3-stable.patch

Patch set for v4.3-stable

Created attachment 12884 [details]
Bug-9959-v4-6-rc2.patch

Updated patch.