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

ADDITIONAL OS VERSION INFORMATION :
Linux 4.6.3-coreos x86_64 GNU/Linux

EXTRA RELEVANT SYSTEM CONFIGURATION :
$ cat /etc/resolv.conf
search default.svc.cluster.local svc.cluster.local cluster.local
nameserver 10.3.0.10
options ndots:5

A DESCRIPTION OF THE PROBLEM :
JNDI DNS resolver doesn't use search list for lookups. Only FQDNs get resolved. "javax.naming.OperationNotSupportedException" occurs when trying to resolve a hostname without specifying the full domain.
This issue seems to be related to http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6427214

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. Add search list to /etc/resolve.conf (http://man7.org/linux/man-pages/man5/resolv.conf.5.html)
2. Try to resolve a DNS SRV record w/o FQDN

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Resolving w/o FQDN with for example nslookup works as expected.

$ nslookup -querytype=srv _redis._tcp.mpe-cache
Server: 10.3.0.10
Address: 10.3.0.10#53

_redis._tcp.mpe-cache.default.svc.cluster.local service = 10 100 6379 mpe-cache.default.svc.cluster.local.

Resolving FQDN with JNDI DNS resolver works also.

$ java Main _redis._tcp.mpe-cache.default.svc.cluster.local
DnsRecord{priority=10, weight=100, port=6379, host='mpe-cache.default.svc.cluster.local.'}

I except the same result w/o FQDN.

ACTUAL -
javax.naming.OperationNotSupportedException: DNS operation not supported [response code 4]; remaining name '_redis._tcp.mpe-cache'
at com.sun.jndi.dns.DnsClient.checkResponseCode(DnsClient.java:659)
at com.sun.jndi.dns.DnsClient.isMatchResponse(DnsClient.java:574)
at com.sun.jndi.dns.DnsClient.doUdpQuery(DnsClient.java:423)
at com.sun.jndi.dns.DnsClient.query(DnsClient.java:208)
at com.sun.jndi.dns.Resolver.query(Resolver.java:81)
at com.sun.jndi.dns.DnsContext.c_getAttributes(DnsContext.java:434)
at com.sun.jndi.toolkit.ctx.ComponentDirContext.p_getAttributes(ComponentDirContext.java:235)
at com.sun.jndi.toolkit.ctx.PartialCompositeDirContext.getAttributes(PartialCompositeDirContext.java:141)
at com.sun.jndi.toolkit.ctx.PartialCompositeDirContext.getAttributes(PartialCompositeDirContext.java:129)
at javax.naming.directory.InitialDirContext.getAttributes(InitialDirContext.java:142)
at Main.main(Main.java:16)

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import javax.naming.NamingEnumeration;
import javax.naming.NamingException;
import javax.naming.directory.Attributes;
import javax.naming.directory.DirContext;
import javax.naming.directory.InitialDirContext;
import java.util.Hashtable;

public class Main {

    public static void main(String[] args) {
        try {
            String service = args[0];
            Hashtable<String, String> env = new Hashtable<>();
            env.put("java.naming.factory.initial", "com.sun.jndi.dns.DnsContextFactory");
            DirContext ctx = new InitialDirContext(env);
            Attributes attrs = ctx.getAttributes(service, new String[]{"SRV"});
            NamingEnumeration<?> servers = attrs.get("srv").getAll();
            while (servers.hasMore()) {
                String[] splitted = ((String) servers.next()).split(" ");
                System.out.println("DnsRecord{" +
                        "priority=" + Integer.parseInt(splitted[0]) +
                        ", weight=" + Integer.parseInt(splitted[1]) +
                        ", port=" + Integer.parseInt(splitted[2]) +
                        ", host='" + splitted[3] + '\'' +
                        '}');
            }
        } catch (NamingException e) {
            e.printStackTrace(System.err);
        }
    }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
The workaround is to use FQDNs.