FULL PRODUCT VERSION :
java version "1.8.0_92"
Java(TM) SE Runtime Environment (build 1.8.0_92-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.92-b14, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 6.1.7601]
Windows 7, Enterprise Edition

EXTRA RELEVANT SYSTEM CONFIGURATION :
Home Kerberos realm: r004.company.net (DC=r004,DC=company,DC=net)
Target Kerberos realm: ad001.company.net (DC=ad001,DC=company,DC=net)

A DESCRIPTION OF THE PROBLEM :
If you connect to a domain controller in your home realm via LDAP and issue a query for another naming context (domain or forest), the server returns either a sub-ordinate (same forest) or an external referral. (different forest) Using GSSAPI or Digest MD5 SASL mech with Context.REFERRAL with follow or throw and ReferralException#getReferralContext() fail to authenticate.

The URL of the referral does not contain a hostname but only a domain name. GSS-API tried to derive an SPN with ldap/a001.company.net, the KDC says "Server not found in database". Digest MD5 fails also, the LDAP server says "LDAP: error code 49 - 80090303: LdapErr: DSID-0C0904BE, comment: The digest-uri does not match any LDAP SPN's registered for this server., data 0, v1db1"
The point is that com.sun.jndi.ldap.LdapCtx is unaware that the URL does not contain a FQDN but a DNS domain name. Active Directory purely relies on DNS SRV discovery from the client side.
Canonicalization with A and PTR records is not a solution because reverse DNS is in Active Directory not really used.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Create an InitialDirContext pointing to ldap://r004.company.net and have a query issued for base DC=ad001,DC=company,DC=net. Set referral handling to follow. LdapCtx will try to follow and fail with Server not in Kerberos database (7).

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Automagically resolve domain name to a hostname and perform the bind.
ACTUAL -
Lower level GSSException with "Server not found in Kerberos database (7)"

ERROR MESSAGES/STACK TRACES THAT OCCUR :
0........e......
.....V0000202B: 
RefErr: DSID-031
00742, data 0, 1
 access points..
ref 1: 'ad001.co
mpany.net'......
........ldap://a
d001.company.net
/CN=AD001-RA005-
AccSvc-G-FgP-GPO
-AccSvc,OU=Group
s,OU=_Central,OU
=AccSvc,OU=RA005
,DC=ad001,DC=com
pany,DC=net

Entered Krb5Context.initSecContext with state=STATE_NEW
Service ticket not found in the subject
>>> Realm doInitialParse: cRealm=[R004.COMPANY.NET], sRealm=[AD001.COMPANY.NET]
>>> Realm parseCapaths: no cfg entry
>>> Credentials acquireServiceCreds: main loop: [0] tempService=krbtgt/AD001.COMPANY.NET@R004.COMPANY.NET
Using builtin default etypes for default_tgs_enctypes
default etypes for default_tgs_enctypes: 17 16 23 1 3.
>>> CksumType: sun.security.krb5.internal.crypto.RsaMd5CksumType
>>> EType: sun.security.krb5.internal.crypto.Aes128CtsHmacSha1EType
getKDCFromDNS using UDP
>>> KrbKdcReq send: kdc=kdc1.r004.company.net. TCP:88, timeout=30000, number of retries =3, #bytes=2490
>>> KDCCommunication: kdc=kdc1.r004.company.net. TCP:88, timeout=30000,Attempt =1, #bytes=2490
>>>DEBUG: TCPClient reading 2458 bytes
>>> KrbKdcReq send: #bytes read=2458
>>> KdcAccessibility: remove kdc1.r004.company.net.:88
>>> EType: sun.security.krb5.internal.crypto.Aes128CtsHmacSha1EType
>>> Credentials acquireServiceCreds: got tgt
>>> Credentials acquireServiceCreds: got right tgt
>>> Credentials acquireServiceCreds: obtaining service creds for ldap/ad001.company.net@AD001.COMPANY.NET
Using builtin default etypes for default_tgs_enctypes
default etypes for default_tgs_enctypes: 17 16 23 1 3.
>>> CksumType: sun.security.krb5.internal.crypto.RsaMd5CksumType
>>> EType: sun.security.krb5.internal.crypto.ArcFourHmacEType
getKDCFromDNS using UDP
>>> KrbKdcReq send: kdc=kdc2.ad001.company.net. TCP:88, timeout=30000, number of retries =3, #bytes=2488
>>> KDCCommunication: kdc=kdc2.ad001.company.net. TCP:88, timeout=30000,Attempt =1, #bytes=2488
>>>DEBUG: TCPClient reading 104 bytes
>>> KrbKdcReq send: #bytes read=104
>>> KdcAccessibility: remove kdc2.ad001.company.net.:88
>>> KDCRep: init() encoding tag is 126 req type is 13
>>>KRBError:
	 sTime is Wed Jun 01 09:26:17 CEST 2016 1464765977000
	 suSec is 176302
	 error code is 7
	 error Message is Server not found in Kerberos database
	 realm is AD001.COMPANY.NET
	 sname is ldap/ad001.company.net
	 msgType is 30
KrbException: Server not found in Kerberos database (7)
KrbException: Fail to create credential. (63) - No service creds
	at sun.security.krb5.internal.CredentialsUtil.acquireServiceCreds(CredentialsUtil.java:299)
	at sun.security.krb5.Credentials.acquireServiceCreds(Credentials.java:454)
	at sun.security.jgss.krb5.Krb5Context.initSecContext(Krb5Context.java:641)
	at sun.security.jgss.GSSContextImpl.initSecContext(GSSContextImpl.java:248)
	at sun.security.jgss.GSSContextImpl.initSecContext(GSSContextImpl.java:179)
	at com.sun.security.sasl.gsskerb.GssKrb5Client.evaluateChallenge(GssKrb5Client.java:193)
	at com.sun.jndi.ldap.sasl.LdapSasl.saslBind(LdapSasl.java:123)
	at com.sun.jndi.ldap.LdapClient.authenticate(LdapClient.java:235)
	at com.sun.jndi.ldap.LdapCtx.connect(LdapCtx.java:2740)
	at com.sun.jndi.ldap.LdapCtx.<init>(LdapCtx.java:316)
	at com.sun.jndi.ldap.LdapCtxFactory.getUsingURL(LdapCtxFactory.java:193)
	at com.sun.jndi.ldap.LdapCtxFactory.getLdapCtxInstance(LdapCtxFactory.java:152)
	at com.sun.jndi.url.ldap.ldapURLContextFactory.getObjectInstance(ldapURLContextFactory.java:52)
	at javax.naming.spi.NamingManager.getURLObject(NamingManager.java:601)
	at javax.naming.spi.NamingManager.processURL(NamingManager.java:381)
	at javax.naming.spi.NamingManager.processURLAddrs(NamingManager.java:361)
	at javax.naming.spi.NamingManager.getObjectInstance(NamingManager.java:333)
	at com.sun.jndi.ldap.LdapReferralContext.<init>(LdapReferralContext.java:111)
	at com.sun.jndi.ldap.LdapReferralException.getReferralContext(LdapReferralException.java:150)
	at com.sun.jndi.ldap.LdapCtx.c_getAttributes(LdapCtx.java:1359)
	at com.sun.jndi.toolkit.ctx.ComponentDirContext.p_getAttributes(ComponentDirContext.java:231)
	at com.sun.jndi.toolkit.ctx.PartialCompositeDirContext.getAttributes(PartialCompositeDirContext.java:139)
	at com.sun.jndi.toolkit.ctx.PartialCompositeDirContext.getAttributes(PartialCompositeDirContext.java:127)
	at javax.naming.directory.InitialDirContext.getAttributes(InitialDirContext.java:142)
	at net.sf.michaelo.dirctxsrc.PartialTEst.main(PartialTEst.java:106)

-> ldap1.company.net:389

0000: 30 05 02 01 05 42 00                               0....B.

Krb5Context.wrap: data=[30 05 02 01 05 42 00 ]
Krb5Context.wrap: token=[05 04 04 ff 00 0c 00 00 00 00 00 00 2f c2 ee e4 30 05 02 01 05 42 00 aa fd 7f d1 22 f6 af d0 a4 35 10 6f ]
Exception in thread "main" javax.naming.AuthenticationException: GSSAPI [Root exception is javax.security.sasl.SaslException: GSS initiate failed [Caused by GSSException: No valid credentials provided (Mechanism level: Fail to create credential. (63) - No service creds)]]
	at com.sun.jndi.ldap.LdapReferralContext.<init>(LdapReferralContext.java:92)
	at com.sun.jndi.ldap.LdapReferralException.getReferralContext(LdapReferralException.java:150)
	at com.sun.jndi.ldap.LdapCtx.c_getAttributes(LdapCtx.java:1359)
	at com.sun.jndi.toolkit.ctx.ComponentDirContext.p_getAttributes(ComponentDirContext.java:231)
	at com.sun.jndi.toolkit.ctx.PartialCompositeDirContext.getAttributes(PartialCompositeDirContext.java:139)
	at com.sun.jndi.toolkit.ctx.PartialCompositeDirContext.getAttributes(PartialCompositeDirContext.java:127)
	at javax.naming.directory.InitialDirContext.getAttributes(InitialDirContext.java:142)
	at net.sf.michaelo.dirctxsrc.PartialTEst.main(PartialTEst.java:106)
Caused by: javax.security.sasl.SaslException: GSS initiate failed [Caused by GSSException: No valid credentials provided (Mechanism level: Fail to create credential. (63) - No service creds)]
	at com.sun.security.sasl.gsskerb.GssKrb5Client.evaluateChallenge(GssKrb5Client.java:212)
	at com.sun.jndi.ldap.sasl.LdapSasl.saslBind(LdapSasl.java:123)
	at com.sun.jndi.ldap.LdapClient.authenticate(LdapClient.java:235)
	at com.sun.jndi.ldap.LdapCtx.connect(LdapCtx.java:2740)
	at com.sun.jndi.ldap.LdapCtx.<init>(LdapCtx.java:316)
	at com.sun.jndi.ldap.LdapCtxFactory.getUsingURL(LdapCtxFactory.java:193)
	at com.sun.jndi.ldap.LdapCtxFactory.getLdapCtxInstance(LdapCtxFactory.java:152)
	at com.sun.jndi.url.ldap.ldapURLContextFactory.getObjectInstance(ldapURLContextFactory.java:52)
	at javax.naming.spi.NamingManager.getURLObject(NamingManager.java:601)
	at javax.naming.spi.NamingManager.processURL(NamingManager.java:381)
	at javax.naming.spi.NamingManager.processURLAddrs(NamingManager.java:361)
	at javax.naming.spi.NamingManager.getObjectInstance(NamingManager.java:333)
	at com.sun.jndi.ldap.LdapReferralContext.<init>(LdapReferralContext.java:111)
	... 7 more
Caused by: GSSException: No valid credentials provided (Mechanism level: Fail to create credential. (63) - No service creds)
	at sun.security.jgss.krb5.Krb5Context.initSecContext(Krb5Context.java:710)
	at sun.security.jgss.GSSContextImpl.initSecContext(GSSContextImpl.java:248)
	at sun.security.jgss.GSSContextImpl.initSecContext(GSSContextImpl.java:179)
	at com.sun.security.sasl.gsskerb.GssKrb5Client.evaluateChallenge(GssKrb5Client.java:193)
	... 19 more
Caused by: KrbException: Fail to create credential. (63) - No service creds
	at sun.security.krb5.internal.CredentialsUtil.acquireServiceCreds(CredentialsUtil.java:299)
	at sun.security.krb5.Credentials.acquireServiceCreds(Credentials.java:454)
	at sun.security.jgss.krb5.Krb5Context.initSecContext(Krb5Context.java:641)
	... 22 more


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import javax.naming.Context;
import javax.naming.NameClassPair;
import javax.naming.NamingEnumeration;
import javax.naming.NamingException;
import javax.naming.directory.Attributes;
import javax.naming.directory.DirContext;
import javax.naming.directory.InitialDirContext;

public class SaslBug {

	public static void main(String[] args) throws NamingException {

		Properties props = new Properties();

		props.put(Context.PROVIDER_URL, "ldap://ldap1.r004.company.net");
		props.put(Context.INITIAL_CONTEXT_FACTORY, "com.sun.jndi.ldap.LdapCtxFactory");
		props.put(Context.SECURITY_AUTHENTICATION, "GSSAPI");
		props.put(Context.REFERRAL, "follow");

		 String roleDn = "CN=AD001-RA005-AccSvc-G-FgP-GPO-AccSvc,OU=Groups,OU=_Central,OU=AccSvc,OU=RA005,DC=ad001,DC=company,DC=net";

		DirContext context = new InitialDirContext(props);

		try {
            Attributes roleAttributes = context.getAttributes(roleDn, new String[] { "groupType",
                    "objectSid;binary", "sIDHistory;binary", "displayName" });
            System.out.println(roleAttributes);
        } catch(NamingException e) {
        	e.printStackTrace();
        }

		context.close();
	}

}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Copied com.sun.jndi.ldap.LdapCtx (based off tag jdk7u101-b00: http://hg.openjdk.java.net/jdk7u/jdk7u/jdk/file/bdcfc4d9ab9f/src/share/classes/com/sun/jndi/ldap/LdapCtx.java), applied the following patch:

===========
Index: com/sun/jndi/ldap/LdapCtx.java
===================================================================
--- com/sun/jndi/ldap/LdapCtx.java	(revision 284)
+++ com/sun/jndi/ldap/LdapCtx.java	(working copy)
@@ -2695,6 +2695,13 @@
                 ldapVersion = (ver != null) ? Integer.parseInt(ver) :
                     DEFAULT_LDAP_VERSION;
 
+                String[] servers = ServiceLocator.getLdapService(hostname, envprops);
+
+                if (servers != null) {
+                    String selectedServer = servers[0];
+                    hostname = selectedServer.substring(0, selectedServer.lastIndexOf('.'));
+                }
+
                 clnt = LdapClient.getInstance(
                     usePool, // Whether to use connection pooling
=========

and added the JAR with -Xbootclasspath/p:...