As someone who programmed Java a couple of years, because work: it is quite doable, since there are now good collection libraries that provide mutable collections (e.g. Google Guava).
Of course, you cannot get the same guarantees that e.g. Haskell provides. Moreover, unless you return concrete types, that Map<> being returned by a method could be mutable or immutable (it's your guess ;), or hopefully in the documentation).
The problem is, as you say, it is quite doable, as long as you have internal access to all of the code. There's no way to ensure that, for example, a function actually returns an immutable map, or actually doesn't modify a map passed to it.
(And no, Collections.immutableMap doesn't.)
(And then there are problems with the JVM bytecode as well - do you know you can pass 2 into a function expecting a boolean? And sometimes it'll get treated as true and sometimes as false? The JVM is "wonderful" like that.)