Do JavaDoc do TreeMap:

Observe que a ordenação mantida por um mapa ordenado (independentemente de um comparador explícito ser fornecido) deve ser consistente com equals se esse mapa ordenado for implementar corretamente a interface Map. (Veja Comparable ou Comparator para uma definição precisa de consistente com equals.) Isto é assim porque a interface Map é definida em termos da operação equals, mas um mapa executa todas as comparações usando seu método compareTo (ou compare), então duas chaves que são considerados iguais por este método são, do ponto de vista do mapa ordenado, iguais. O comportamento de um mapa ordenado é bem definido, mesmo que sua ordenação seja inconsistente com os iguais; ele simplesmente não obedece ao contrato geral da interface do Mapa.

Alguém pode dar um exemplo concreto para avaliar o problema que pode ocorrer se a ordenação não for consistente com iguais? Tomemos por exemplo classe definida pelo usuário que tem uma ordenação natural, ou seja, implementa Comparable. Além disso, todas as classes internas no JDK mantêm essa invariante?