OK so after some more Googling we found out that this is due to:
https://issues.apache.org/jira/browse/ZOOKEEPER-1696
An issue with the combination WebLogic / Zookeeper when not using SASL.
The Zookeeper Jira above links to a fix on the Zookeeper source, which unfortunately we can not use as we have to run with Cloudera CDH 4.2.2
Most likely we will switch to JBoss. At least JBoss 5 (the very lowest version we can run) does not show this issue. We will also try JBoss 6 & 7, see what happens then.
Will accept this as the answer, hopefully it will be useful for someone.