It seems that this issue is caused by an bug in Android itself which should be fixed!? The issue and its fix is descriped here: Android issue 24672
So adding this piece of code to my OkHttp URLConnection factory fixed the issue right away:
@Override protected HttpURLConnection createConnection(URL url) throws IOException {
HttpURLConnection connection = client.open(url);
// Fix for bug in Android runtime(!!!):
// https://code.google.com/p/android/issues/detail?id=24672
connection.setRequestProperty("Accept-Encoding", "");
return connection;
}