Several well-known Java gurus have advocated this, eg. Joshua Bloch. I worked with Ken Arnold for a bit, and a lot of the code he wrote was in this style.
The problem is that you're usually using Java because you want access to all those Java libraries, and the vast majority of Java libraries do not use this style. So you get state leaking into your program even if your own code doesn't do it.
(This is also why I'm less thrilled by Clojure than many other people are, even though I think it's a very well-designed language. The reason people are into Clojure is because it can use Java libraries and yet provides a mostly-functional language on top. But the problem isn't in Java-the-language, it's in Java libraries themselves. Unless you go rewrite the offending libraries - and this includes most of Swing, JSF, JFreeChart, the JavaBeans spec, and Calendar - you'll still run into problems. The only major libraries I've seen that use a relatively stateless style are Date and Java Collections Frameworks (both done by Josh Bloch, not surprisingly), JavaSpaces (done by Ken), and the basic String and Number classes.
This, again, assumes you can trust your libraries. A single method that doesn't follow this convention will pollute anything that calls it.
I've done things like this, in Python and to a lesser extent in Java. It works. It is pretty easy to slip up - I've had some bugs introduced because I forgot to copy a list - but it's at least a tractable problem. Gets easier if you use things like list comprehensions and slicing, which copy by default. Though Java's lack of support for closures can make this difficult.
Not everyone gets to choose their language. When I do, it's usually something saner than Java.