Yeah, well.
To put some kind of closure to it, it appears Jens is right about the Java 6 API use.
I tried to be super-smart by running gwt-servlet.jar through retrotranslator - which can also verify the result against a given classpath.
Turns out there are several occasions where String.getBytes(Charset), String.isEmpty, java.util.Deque is being used in GWT 2.5. server-side codebase.
Bummer, at least this finally confirms that anyone doomed to still use Java 5 based servers will be unable to user anything newer than GWT 2.4 from this point on.
That's really disappointing...