In my opinion, your rule is a good one (or at least it's not a bad one), but only because of the situation you are describing. I wouldn't say that I agree with it in all situations, so, from the standpoint of my inner pedant, I'd have to say your rule is technically too broad.
Typically you wouldn't define immutable objects unless they are essentially being used as data transfer objects (DTO), which means that they contain data properties but very little logic and no dependencies. If that is the case, as it seems it is here, I'd say you are safe to use the concrete types directly rather than interfaces.
I'm sure there will be some unit-testing purists who will disagree, but in my opinion, DTO classes can be safely excluded from unit-testing and dependency-injection requirements. There is no need to use a factory to create a DTO, since it has no dependencies. If everything creates the DTOs directly as needed, then there's really no way to inject a different type anyway, so there's no need for an interface. And since they contain no logic, there's nothing to unit-test. Even if they do contain some logic, as long as they have no dependencies, then it should be trivial to unit-test the logic, if necessary.
As such, I think that making a rule that all DTO classes shall not implement an interface, while potentially unnecessary, is not going to hurt your software design. Since you have this requirement that the data needs to be immutable, and you cannot enforce that via an interface, then I would say it's totally legitimate to establish that rule as a coding standard.
The larger issue, though, is the need to strictly enforce a clean DTO layer. As long as your interface-less immutable classes only exist in the DTO layer, and your DTO layer remains free of logic and dependencies, then you will be safe. If you start mixing your layers, though, and you have interface-less classes that double as business layer classes, then I think you will start to run into much trouble.
- Java classes are similar to C++ as described in the third paragraph. Java interfaces are a different concept.
- In Java, a class implicitly specifies both an interface in the GoF sense and the implementation. By contrast a Java interface explicitly specifies an interface in the GoF sense and doesn't specify an implementation. In both cases inheritance implies interface inheritance. Only in the case of class inheritance does it imply implementation inheritance.
For a better example of the distinction, I highly recommend learning just enough Ruby to understand how a class can use method_missing to proxy off of an unrelated object. This provides a very explicit example of interface inheritance without implementation inheritance. (Bonus, Ruby's OO model is the same as Smalltalk's while having a more familiar syntax, which gives you a leg up on the rest of the book.)
Best Answer
The FAQ provides the answer. In short, they saw a potential combinatorial explosion of needed interfaces with modifiable, unmodifiable view, delete-only, add-only, fixed-length, immutable (for threading), and so on for each possible set of implemented option methods.